其实是比较裸的矩乘了（就是多了一个分段），就是有一些处理的方法值得注意
一般凡是+*+*的递推dp似乎都可以矩乘
注意快速幂的 单位矩阵、
另外并不是只有完全静止的转移才能进行转移、
如果是以1为周期的变化是可以写进矩阵里伴随转移的
注意分段思想的应用呢。，基本是个数学题就会让你用类似分段的思想搞、
mdzz：开着运行调试，，错的莫名思议
i和k打反了
long long
码（极其难看）：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; long long n,m; struct jz { long long p[5][5],c,k; }a,b,u,ans; jz operator *(jz x,jz y) { //cout<<u.p[1][1]<<" "; for(int i=0;i<=4;i++) for(int j=0;j<=4;j++) u.p[i][j]=0; // cout<<u.p[1][1]; u.c=y.c; u.k=x.k; for(int i=1;i<=x.k;i++) for(int j=1;j<=x.c;j++) for(int k=1;k<=y.c;k++) { u.p[i][k]=(u.p[i][k]+x.p[i][j]*y.p[j][k]%m)%m; } //cout<<u.p[1][1]<<" "; return u; } jz operator ^(jz x,long long ci) { ans=x; ans.c=3; ans.k=3; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(i==j)ans.p[i][i]=1; else ans.p[i][j]=0; while(ci!=0) { if(ci&1==1)ans=ans*x; ci>>=1; x=x*x; } return ans; } int main() { scanf("%lld%lld",&n,&m); a.c=1; a.k=3; b.c=3; b.k=3; a.p[3][1]=a.p[2][1]=1; for(int i=1;i<=3;i++) for(int j=i;j<=3;j++) b.p[i][j]=1; b.p[1][3]=0; for(long long i=10;;i*=10) { long long k=i%m;//cout<<i; b.p[1][1]=k; long long ci= i/10*9; if(i>n)ci=n-i/10+1; a=(b^ci)*a; if(i>n)break; } printf("%lld",a.p[1][1]); }
