Considering violence, then there is f (n) = (f (n-1) *10).digit+n)%m。Note that each shift is similar, taking into account the fast power of the matrix. First of all, we separate the number of digits separately, obviously it is only log. Then we get the recurrence formula of F (n) =a. F (n-1) +b, and we can get the fast power of matrix. Notice that the B here is changing, but every time it changes.The same volume, adding one dimension to the matrix is fine.
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define ll long long ll n;int m; struct matrix { int n,a[3][3]; matrix operator *(const matrix&b) const { matrix c;c.n=n;memset(c.a,0,sizeof(c.a)); for (int i=0;i<n;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j]%m)%m; return c; } }f,a; int main() { #ifndef ONLINE_JUDGE freopen("bzoj2326.in","r",stdin); freopen("bzoj2326.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif cin>>n>>m;if (m==1) {cout<<0;return 0;} ll t=10; f.n=1;f.a[0][0]=0,f.a[0][1]=1,f.a[0][2]=1; while (t<=n) { a.n=3;a.a[0][0]=t%m;a.a[0][1]=a.a[0][2]=0; a.a[1][0]=a.a[1][1]=1,a.a[1][2]=0; a.a[2][0]=0,a.a[2][1]=1,a.a[2][2]=1; for (ll k=t-t/10;k;k>>=1,a=a*a) if (k&1) f=f*a; t*=10; } a.n=3;a.a[0][0]=t%m;a.a[0][1]=a.a[0][2]=0; a.a[1][0]=a.a[1][1]=1,a.a[1][2]=0; a.a[2][0]=0,a.a[2][1]=1,a.a[2][2]=1; for (ll k=n-t/10+1;k;k>>=1,a=a*a) if (k&1) f=f*a; cout<<f.a[0][0]; return 0; }