题目大意：已知递推公式和边缘值，求某项的最后m(0<m<5)位数字。

题目分析：矩阵二分幂的模板题。

 

代码如下：

1 # include
     
       2 # include
      
        3 # include
       
         4 # include
        
          5 using namespace std; 6 struct matrix 7 { 8     int r,c,m[3][3]; 9     matrix(int _r,int _c):r(_r),c(_c){}10 };11 int a,b,n,m;12 int mod[4]={
   10,100,1000,10000};13 matrix multiply(matrix a,matrix b)14 {15     matrix c(a.r,b.c);16     for(int i=1;i<=c.r;++i){17         for(int j=1;j<=c.c;++j){18             c.m[i][j]=0;19             for(int k=1;k<=a.c;++k){20                 c.m[i][j]+=(a.m[i][k]*b.m[k][j]);21                 c.m[i][j]%=mod[m-1];22             }23         }24     }25     return c;26 }27 matrix matrix_pow(matrix a,int k)28 {29     if(k==0){30         for(int i=1;i<=a.r;++i)31             for(int j=1;j<=a.c;++j)32                 a.m[i][j]=(i==j)?1:0;33         return a;34     }35     if(k==1)36         return a;37     matrix res=matrix_pow(a,k/2);38     res=multiply(res,res);39     if(k&1)40         res=multiply(res,a);41     return res;42 }43 int main()44 {45     int T;46     scanf("%d",&T);47     while(T--)48     {49         scanf("%d%d%d%d",&a,&b,&n,&m);50         if(n==0){51             printf("%d\n",a%mod[m-1]);52             continue;53         }54         matrix mat(2,2);55         mat.m[1][1]=mat.m[1][2]=mat.m[2][1]=1,mat.m[2][2]=0;56         mat=matrix_pow(mat,n-1);57         matrix ans(2,1);58         ans.m[1][1]=b,ans.m[2][1]=a;59         ans=multiply(mat,ans);60         printf("%d\n",ans.m[1][1]);61     }62     return 0;63 }