hdu 1005 根据递推公式构造矩阵 ( 矩阵快速幂)-白红宇

hdu 1005 根据递推公式构造矩阵 ( 矩阵快速幂)

阅读量：4326 次

发布时间：2019-06-06

本文共 1753 字，大约阅读时间需要 5 分钟。

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Sample Input

1 1 3 //a b n

1 2 10

0 0 0

Sample Output

矩阵A * 矩阵B = 矩阵C

a b f(n-1) f(n)

1 0 f(n-2) f(n-1)

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
          5 # include 
          
            6 # define LL long long 7 using namespace std ; 8  9 const int MOD = 7 ;10 11 struct Matrix12 {13     int mat[2][2];14 };15 16 Matrix mul(Matrix a,Matrix b) //矩阵乘法17 {18     Matrix c;19     for(int i=0;i<2;i++)20         for(int j=0;j<2;j++)21         {22             c.mat[i][j]=0;23             for(int k=0;k<2;k++)24             {25                 c.mat[i][j]=(c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%(MOD);26             }27         }28     return c;29 }30 Matrix pow_M(Matrix a,int k)  //矩阵快速幂31 {32     Matrix ans;33     memset(ans.mat,0,sizeof(ans.mat));34     for (int i=0;i<2;i++)35         ans.mat[i][i]=1;36     Matrix temp=a;37     while(k)38     {39         if(k&1)ans=mul(ans,temp);40         temp=mul(temp,temp);41         k>>=1;42     }43     return ans;44 }45 46 47 48 int main ()49 {50    // freopen("in.txt","r",stdin) ;51     int a,b,n;52     while(scanf("%d%d%d" , &a,&b,&n) != EOF)53     {54         if (a==0 && b==0 && n==0)55             break ;56         if (n <= 2)57         {58             printf("1\n") ;59             continue ;60         }61         Matrix t ;62         t.mat[0][0] = a ;63         t.mat[0][1] = b ;64         t.mat[1][0] = 1 ;65         t.mat[1][1] = 0 ;66         Matrix ans = pow_M(t,n-2) ;67         printf("%d\n" , (ans.mat[0][0] + ans.mat[0][1])%MOD) ;68 69     }70 71 72     return 0 ;73 }