转载请注明出处：

 

[HNOI2011] 数学作业

时间限制：1 s   内存限制：128 MB

【题目描述】

solution：

    用矩阵乘。

    在向后插入数时，相当于把原答案乘10的多少次方再加上这个数，所以我们可以导成矩阵。

    

        a矩阵                                  b矩阵

       

         ans                            10^j     1      0

  

          i                               0      1      1

          1                               0      0      1

    b矩阵第一行是把ans*10^j+i，第二行是让i加1，第三行是保持a[3]=1.

    由于10^j的j不同，所以我们应分层去求。

    然后我们就可以开心地矩阵快速幂了。

    注意时刻取模。

附上代码：

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;long long ans,a[10],b[10][10],n,mod;void ksc(long long);void hucheng();void zicheng();int main(){ scanf("%lld%lld",&n,&mod); long long x=10,y=10,z=9; a[2]=1; a[3]=1; while(x<=n) { memset(b,0,sizeof(b)); b[1][1]=y; b[1][2]=b[2][2]=b[2][3]=b[3][3]=1; ksc(z); ans=a[1]; x*=10; y*=10; y%=mod; z*=10; } memset(b,0,sizeof(b)); b[1][1]=y; b[1][2]=b[2][2]=b[2][3]=b[3][3]=1; ksc(n-x/10+1); printf("%lld",a[1]); return 0;}void ksc(long long x){ while(x) { if((x&1)==1) hucheng(); x=x>>1; zicheng(); }}void hucheng(){ long long c[7]; memset(c,0,sizeof(c)); for(long long i=1;i<=3;i++) for(long long j=1;j<=3;j++) { c[i]+=a[j]*b[i][j]; c[i]%=mod; } for(long long i=1;i<=3;i++) a[i]=c[i];}void zicheng(){ long long c[7][7]; memset(c,0,sizeof(c)); for(long long i=1;i<=3;i++) for(long long j=1;j<=3;j++) for(long long k=1;k<=3;k++) { c[i][j]+=b[i][k]*b[k][j]; c[i][j]%=mod; } for(long long i=1;i<=3;i++) for(long long j=1;j<=3;j++) b[i][j]=c[i][j];}