矩阵这玩意儿太腻害了……非得我冥（kan）思（le）苦（ti）想（jie）才会……
先考虑递推方程$f[n]=f[n-1]*10^{len(n)}+n$
然后用矩阵加速
$$egin{bmatrix}f[n]&n&1end{bmatrix}=egin{bmatrix}f[n-1]&n-1&1end{bmatrix}*egin{bmatrix}10^{len(n)}&0&0\ 1&1&0\ 1&1&1end{bmatrix}$$
然而问题就来了，$10^{len(n)}$怎么搞？
那么只能枚举了……
枚举一下位数，就代表$10^{len(n)}$是多少，然后带进去乱搞
好烦啊……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define ll long long 6 using namespace std; 7 ll mod; 8 struct Matrix{ 9 ll n,m,a[5][5]; 10 Matrix(ll x,ll y){ 11 n=x,m=y,memset(a,0,sizeof(a)); 12 } 13 Matrix(ll x,ll y,char E){ 14 n=x,m=y,memset(a,0,sizeof(a)); 15 for(int i=1;i<=n;++i) a[i][i]=1; 16 } 17 ll* operator [](const ll x){return a[x];} 18 inline Matrix operator *(Matrix b){ 19 Matrix res(n,b.m); 20 for(int i=1;i<=n;++i) 21 for(int j=1;j<=b.m;++j) 22 for(int k=1;k<=m;++k) 23 (res[i][j]+=a[i][k]*b[k][j])%=mod; 24 return res; 25 } 26 inline void operator *=(Matrix b){ 27 *this=*this*b; 28 } 29 Matrix operator ^(ll b){ 30 Matrix res(n,m,'e'),a=*this; 31 while(b){ 32 if(b&1) res*=a; 33 a*=a,b>>=1; 34 } 35 return res; 36 } 37 }; 38 ll n; 39 int glen(ll x){ 40 int l=0; 41 while(x) ++l,x/=10; 42 return l; 43 } 44 ll pow10(int x){ 45 ll res=1; 46 while(x--) res*=10; 47 return res; 48 } 49 int main(){ 50 cin>>n>>mod; 51 Matrix A(1,3); 52 int len=glen(n); 53 A[1][1]=A[1][2]=A[1][3]=1; 54 for(int i=0;i<len-1;++i){ 55 Matrix B(3,3); 56 B[1][1]=pow10(i+1)%mod; 57 B[2][1]=B[2][2]=B[3][1]=B[3][2]=B[3][3]=1; 58 ll m=pow10(i+1)-pow10(i); 59 A*=(B^(m-(i==0?1:0))); 60 } 61 Matrix B(3,3); 62 B[1][1]=pow10(len)%mod; 63 B[2][1]=B[2][2]=B[3][1]=B[3][2]=B[3][3]=1; 64 ll m=n-pow10(len-1)+1; 65 A*=(B^(m-(len-1==0?1:0))); 66 printf("%lld ",A[1][1]); 67 return 0; 68 }