【bzoj2326】【HNOI2011】【数学作业】【矩阵乘法】

题解：设f[i]为连上第i个数之后的值。

显然f[i]=f[i-1]*10^k+i;

然后我们根据k分组。每一组内直接矩乘即可。

代码：

#include<cstdio>
#include<cstring>
using namespace std;
long long n,m,a[4][4],b[4][4],t(10);
long long mul(long long x,long long y){long long ans(0);while (y){if (y&1) (ans+=x)%=m;(x+=x)%=m;y>>=1;}return ans;
}
void cheng(long long a[4][4],long long b[4][4],long long s[4][4]){long long c[4][4];for(int i=1;i<=3;i++)for(int j=1;j<=3;j++){c[i][j]=0;for(int k=1;k<=3;k++)c[i][j]=(c[i][j]+mul(a[i][k],b[k][j]))%m;}for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)s[i][j]=c[i][j];
}
void work(long long t,long long pre){memset(b,0,sizeof(b));b[1][1]=t;b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;long long y=pre-t/10+1;while(y){if(y&1)cheng(a,b,a);cheng(b,b,b);y>>=1;}
}
int main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=3;i++)a[i][i]=1;while(n>=t){work(t,t-1);t*=10;}work(t,n);printf("%lld",a[3][1]);
}