矩阵乘法。。
这个矩阵的构造有点麻烦。。关键就从n转移到n-1（其实是我题做得少。。
分位数统计即可
1 #include<bits/stdc++.h> 2 #define inc(i,l,r) for(int i=l;i<=r;i++) 3 #define dec(i,l,r) for(int i=l;i>=r;i--) 4 #define link(x) for(edge *j=h[x];j;j=j->next) 5 #define mem(a) memset(a,0,sizeof(a)) 6 #define ll long long 7 #define succ(x) (1<<x) 8 #define lowbit(x) (x&(-x)) 9 using namespace std; 10 ll read(){ 11 ll x=0,f=1;char ch=getchar(); 12 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 13 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 14 return x*f; 15 } 16 struct mat{ 17 ll a[4][4]; 18 }tmp,t; 19 ll n,m,k,inf; 20 mat operator*(const mat&x,const mat&y){ 21 mat s;mem(s.a); 22 inc(i,1,3) 23 inc(j,1,3) 24 inc(k,1,3)s.a[i][j]=(x.a[i][k]*y.a[k][j]%inf+s.a[i][j]+inf)%inf; 25 return s; 26 } 27 void out(mat x){ 28 inc(i,1,3){inc(j,1,3)printf("%lld ",x.a[i][j]);putchar(' '); 29 }putchar(' '); 30 } 31 int main(){ 32 freopen("data.in","r",stdin); 33 inc(i,1,3)tmp.a[i][i]=1; 34 t.a[2][2]=t.a[1][3]=t.a[3][3]=t.a[3][2]=1; 35 m=n=read();inf=read();m%=inf; 36 for(k=1;k<=n&&k;k*=10){ 37 ll _t=min(k*10-1,n); 38 t.a[1][1]=10*k%inf;ll v=_t-k+1; 39 // out(t); 40 for(mat s=t;v;v>>=1,s=s*s)if(v&1)tmp=s*tmp; 41 // out(tmp); 42 } 43 printf("%lld ",(tmp.a[1][3]+tmp.a[1][2]+inf)%inf); 44 return 0; 45 }