hdu4549 M斐波那契数列 矩阵快速幂+快速幂

M斐波那契数列F[n]是一种整数数列，它的定义如下：

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n，你能求出F[n]的值吗？

通过简单地列出若干项 F 即可发现，某一项的值是由若干 a 和 b 相乘得到的，而他们的指数是连续的两项斐波那契数。

因此可以通过斐波那契数列的矩阵快速幂求法得到，注意需要指数的降幂公式。

 #include<stdio.h>

 #include<string.h>

 typedef long long ll;

 const int mod=;

 const int mmod=;

 struct mat{

     int r,c;

     ll m[][];

     void clear(){

         for(int i=;i<=r;i++)memset(m[i],,sizeof(m[i]));

     }

 };

 int read(){

     int x=;

     char c=getchar();

     while(c>''||c<'')c=getchar();

     while(c>=''&&c<=''){

         x=x*+c-'';

         c=getchar();

     }

     return x;

 }

 mat MatMul(mat &m1,mat &m2){

     mat tmp;

     tmp.r=m1.r;

     tmp.c=m2.c;

     int i,j,k;

     for(i=;i<=tmp.r;i++){

         for(j=;j<=tmp.c;j++){

             ll t=;

             for(k=;k<=m1.c;k++){

                 t=(t+(m1.m[i][k]*m2.m[k][j])%mmod)%mmod;

             }

             tmp.m[i][j]=t;

         }

     }

     return tmp;

 }

 mat MatQP(mat &a,int n){

     mat ans,tmp=a;

     ans.r=ans.c=a.r;

     memset(ans.m,,sizeof(ans.m));

     for(int i=;i<=ans.r;i++){

         ans.m[i][i]=;

     }

     while(n){

         if(n&)ans=MatMul(ans,tmp);

         n>>=;

         tmp=MatMul(tmp,tmp);

     }

     return ans;

 }

 ll QP(ll a,ll n){

     ll tmp=a,ans=;

     while(n){

         if(n&)ans=ans*tmp%mod;

         tmp=tmp*tmp%mod;

         n>>=;

     }

     return ans%mod;

 }

 int main(){

     int x,y,n;

     mat t,tmp;

     t.r=;t.c=;

     t.clear();

     t.m[][]=t.m[][]=t.m[][]=;

     mat a;

     a.r=;

     a.c=;

     a.m[][]=;

     a.m[][]=;

     ll ans;

     while(scanf("%d%d%d",&x,&y,&n)!=EOF){

         if(n==)printf("%d\n",x);

         else{

             tmp=MatQP(t,n-);

             tmp=MatMul(tmp,a);

             ans=QP(x,tmp.m[][])*QP(y,tmp.m[][])%mod;

             printf("%lld\n",ans);

         }

     }

     return ;

 }