题目链接：bzoj2326 题目大意： 给N，M。求出将1,2,…,N按顺序连在一起得到的数mod M的值。比如N是13的话，这个数就是12345678910111213。
题解： 矩乘%hyc 可以得知，答案ans=ans*10^(j的位数）+j，j=1 to N，再mod个M嘛。 于是我们可以构造一个↓这样的矩阵 × ans存的就是答案，而j就表示将要把j这个数连进去。 但因为j的位数会改变，即x就会改变。于是我们可以把位数相同的放在一起做一遍矩阵快速幂，然后修改a[0][0]这个位置的值，再继续搞就好了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; struct matrix { LL a[3][3];int l,r; matrix() {memset(a,0,sizeof(a));} }; matrix gg;LL n,mod; matrix multt(matrix x,matrix y) { matrix ret;int i,j,k; ret.l=x.l;ret.r=y.r; for (i=0;i<ret.l;i++) for (j=0;j<ret.r;j++) { for (k=0;k<y.l;k++) ret.a[i][j]+=x.a[i][k]*y.a[k][j]; ret.a[i][j]%=mod; } return ret; } matrix qpow(matrix x,LL tt) { matrix ret;ret.l=ret.r=3; ret.a[0][0]=ret.a[1][1]=ret.a[2][2]=1; while (tt) { if (tt&1) ret=multt(ret,x); x=multt(x,x);tt>>=1; } return ret; } int main() { int i,tj;LL t,ww; scanf("%lld%lld",&n,&mod); memset(gg.a,0,sizeof(gg)); gg.l=gg.r=3;t=n;tj=0;ww=1; gg.a[0][0]=10;gg.a[0][1]=gg.a[1][1]=gg.a[1][2]=gg.a[2][2]=1; while (t) tj++,t/=10; matrix ans; ans.l=3;ans.r=1; ans.a[0][0]=0; ans.a[1][0]=1; ans.a[2][0]=1; for (i=1;i<tj;i++) { matrix now=qpow(gg,ww*9); ans=multt(now,ans); gg.a[0][0]=(gg.a[0][0]*10)%mod; ww*=10; } matrix now=qpow(gg,n-ww+1); ans=multt(now,ans); printf("%lld\n",ans.a[0][0]); return 0; }