??线性代数太烂了。。。这个逼题居然卡了半天才做出来，弱的不行啊。。。
矩阵快速幂，把n这个len位数拆成len次分段快速幂就可以了。
注意取模的数字m<=1e9，所以矩阵乘法运算时要先对乘数取模，防止中间运算结果太大溢出，坑爹啊
代码：
#include#include #include #include #include #define MAXN 4 using namespace std; typedef long long int LL; int mod; struct matrix { LL p[MAXN][MAXN]; }ans,tmp; matrix operator*(matrix a,matrix b) { matrix c; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { c.p[i][j]=0; for(int k=1;k<=3;k++) c.p[i][j]=(c.p[i][j]+((a.p[i][k]%mod)*(b.p[k][j]%mod))%mod)%mod; } return c; } void cal(LL t,LL last) //从last-t/10计算到last { memset(tmp.p,0,sizeof(tmp.p)); tmp.p[1][1]=t; tmp.p[2][1]=tmp.p[3][1]=tmp.p[2][2]=tmp.p[3][2]=tmp.p[3][3]=1; LL y=last-t/10+1; while(y) { if(y&1) ans=ans*tmp; tmp=tmp*tmp; y>>=1; } } int main() { for(int i=1;i<=3;i++) ans.p[i][i]=1; LL n; scanf("%lld%lld",&n,&mod); LL t=10; while(n>=t) { cal(t,t-1); t*=10; } cal(t,n); printf("%lld\n",ans.p[3][1]); return 0; }