朴素数位 DP
一个显然的 DP：设 $\textit{dp}_{i,j},i\in[1,k],j\in[0,9]$ 为 $i$ 位且最高位为 $j$ 的 Sam 数的个数。
则有：
\[\textit{dp}_{i,j}=\sum_{\max(j-2,0)}^{\min(j+2,9)}\textit{dp}_{i-1,j}\]最终答案 $\textit{ans}$ 为：
\[\textit{ans}=\sum_{i=1}^9\textit{dp}_{k,i}+[k=1]\textit{dp}_{k,0}\]因为当 $k\neq1$ 时，最高位不能取 $0$。只有 $k=1$ 时，Sam 数为一位数，最高位可以是 $0$。
而边界情况即 $k=1$ 时的答案：
\[\textit{dp}_{1,i}=1\]这样的复杂度是 $\mathcal O(k)$ 的。
矩阵加速 DP
考虑到 $1\leq k\leq10^{18}$，这个 DP 需要优化。
容易发现 $\textit{dp}_{i,j}$ 只与常数级别的其他值有关，且是线性递推，且每次转移都是确定的，因此可以考虑矩阵加速 DP。
根据上面的递推式，可以构矩阵： \(\begin{bmatrix} 1&1&1&0&0&0&0&0&0&0\\ 1&1&1&1&0&0&0&0&0&0\\ 1&1&1&1&1&0&0&0&0&0\\ 0&1&1&1&1&1&0&0&0&0\\ 0&0&1&1&1&1&1&0&0&0\\ 0&0&0&1&1&1&1&1&0&0\\ 0&0&0&0&1&1&1&1&1&0\\ 0&0&0&0&0&1&1&1&1&1\\ 0&0&0&0&0&0&1&1&1&1\\ 0&0&0&0&0&0&0&1&1&1\\ \end{bmatrix} \begin{bmatrix} dp_{i,0}\\dp_{i,1}\\dp_{i,2}\\dp_{i,3}\\dp_{i,4}\\dp_{i,5}\\dp_{i,6}\\dp_{i,7}\\dp_{i,8}\\dp_{i,9} \end{bmatrix} = \begin{bmatrix} dp_{i+1,0}\\dp_{i+1,1}\\dp_{i+1,2}\\dp_{i+1,3}\\dp_{i+1,4}\\dp_{i+1,5}\\dp_{i+1,6}\\dp_{i+1,7}\\dp_{i+1,8}\\dp_{i+1,9} \end{bmatrix}\)
因此，可以直接得出：
\[\begin{bmatrix} 1&1&1&0&0&0&0&0&0&0\\ 1&1&1&1&0&0&0&0&0&0\\ 1&1&1&1&1&0&0&0&0&0\\ 0&1&1&1&1&1&0&0&0&0\\ 0&0&1&1&1&1&1&0&0&0\\ 0&0&0&1&1&1&1&1&0&0\\ 0&0&0&0&1&1&1&1&1&0\\ 0&0&0&0&0&1&1&1&1&1\\ 0&0&0&0&0&0&1&1&1&1\\ 0&0&0&0&0&0&0&1&1&1\\ \end{bmatrix}^{k-1} \begin{bmatrix} dp_{1,0}\\dp_{1,1}\\dp_{1,2}\\dp_{1,3}\\dp_{1,4}\\dp_{1,5}\\dp_{1,6}\\dp_{1,7}\\dp_{1,8}\\dp_{1,9} \end{bmatrix} = \begin{bmatrix} dp_{k,0}\\dp_{k,1}\\dp_{k,2}\\dp_{k,3}\\dp_{k,4}\\dp_{k,5}\\dp_{k,6}\\dp_{k,7}\\dp_{k,8}\\dp_{k,9} \end{bmatrix}\]又注意到 $\textit{dp}{1,0}=\textit{dp}{1,2}=\cdots=\textit{dp}_{1,9}=1$，因此可以 $\mathcal O\left(\log k\right)$ 求出答案。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int V=10,P=1e9+7;
ll n;
//n 行 m 列
struct Matrix{
int n,m;
//下标从 1 开始.
int a[V+1][V+1];
Matrix(){
memset(a,0,sizeof(a));
}
Matrix(int nn,int mm=-1){
memset(a,0,sizeof(a));
n=nn;m=mm;
if(m==-1){
m=n;
}
}
void print(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cerr<<a[i][j]<<' ';
}
cerr<<endl;
}
}
};
Matrix operator *(Matrix A,Matrix B){
Matrix C(A.n,B.m);
for(int i=1;i<=A.n;i++){
for(int j=1;j<=B.m;j++){
for(int k=1;k<=A.m;k++){
C.a[i][j]=(C.a[i][j]+1ll*A.a[i][k]*B.a[k][j])%P;
}
}
}
return C;
}
Matrix qpow(Matrix base,ll n){
Matrix ans(base.n);
for(int i=1;i<=base.n;i++){
ans.a[i][i]=1;
}
while(n){
if(n&1){
ans=ans*base;
}
base=base*base;
n>>=1;
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
Matrix A(V,V);
for(int i=1;i<=V;i++){
for(int j=max(i-2,1);j<=min(i+2,V);j++){
A.a[i][j]=1;
}
}
A=qpow(A,n-1);
Matrix B(V,1);
for(int i=1;i<=V;i++){
B.a[i][1]=1;
}
B=A*B;
int ans=0;
for(int i=1+(n!=1);i<=V;i++){
ans=(ans+B.a[i][1])%P;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
