solution
矩阵：
f： a：
10^k 0 0
ans i 1 * 1 1 0
1 1 1
分段乘，给a赋值10^k时记得给10^k%上mod，不然炸long long了
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define ll long long 5 #define chua(k) a[1][1]=p[k]%mod;a[1][2]=a[1][3]=a[2][3]=0;a[2][1]=a[2][2]=a[3][2]=a[3][3]=a[3][1]=1 6 using namespace std; 7 8 ll n; 9 ll mod,weishu; 10 ll f[5],a[5][5],temp[5][5]; 11 ll p[101],ci[101]; 12 13 void out11() 14 { 15 printf(" "); 16 for(int i=1;i<=3;++i) 17 printf("%lld ",f[i]); 18 printf(" "); 19 for(int i=1;i<=3;++i) 20 { 21 for(int j=1;j<=3;++j) 22 printf("%lld ",a[i][j]); 23 printf(" "); 24 } 25 printf(" "); 26 } 27 28 void work() 29 { 30 p[1]=10;ci[1]=9; 31 for(int i=2;i<=18;++i) 32 { 33 p[i]=p[i-1]*10; 34 ci[i]=ci[i-1]*10; 35 //cout<<ci[i]<<endl; 36 } 37 38 for(ll i=n;i;i/=10) 39 ++weishu; 40 41 ci[weishu]=n-p[weishu-1]+1; 42 43 //cout<<weishu<<endl; 44 45 //for(int i=2;i<=18;++i) 46 // cout<<ci[i]<<endl; 47 48 49 50 //cout<<weishu<<endl; 51 52 f[1]=0;f[2]=0;f[3]=1; 53 for(int l=1;l<=weishu;++l) 54 { 55 chua(l); 56 57 while(ci[l]) 58 { 59 //out11(); 60 61 if(ci[l]&1) 62 { 63 for(int i=1;i<=3;++i) 64 { 65 temp[1][i]=0; 66 for(int k=1;k<=3;++k) 67 //temp[1][i]=(temp[1][i]+f[k]*a[k][i]); 68 temp[1][i]=(temp[1][i]+f[k]*a[k][i]%mod)%mod; 69 } 70 for(int i=1;i<=3;++i) 71 f[i]=temp[1][i]; 72 } 73 74 for(int i=1;i<=3;++i) 75 for(int j=1;j<=3;++j) 76 { 77 temp[i][j]=0; 78 for(int k=1;k<=3;++k) 79 temp[i][j]=(temp[i][j]+a[i][k]*a[k][j]%mod)%mod; 80 //temp[i][j]=(temp[i][j]+a[i][k]*a[k][j]); 81 } 82 for(int i=1;i<=3;++i) 83 for(int j=1;j<=3;++j) 84 a[i][j]=temp[i][j]; 85 86 ci[l]>>=1; 87 } 88 } 89 } 90 91 int main(){ 92 93 // freopen("1.txt","r",stdin); 94 //freopen("2.txt","w",stdout); 95 96 scanf("%lld%lld",&n,&mod); 97 work(); 98 printf("%lld",f[1]); 99 return 0; 100 }