HDU4291—A Short problem

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4291

题目意思：求g(g(g(n))) mod 10⁹ + 7，其中g(n) = 3g(n - 1) + g(n - 2)，g(1) = 1，g(0) = 0。

思路：一个很简单的矩阵快速幂，简单的想法就是先用n算出g(n)，然后再算g（g（n）），然后再算最外层，都是mod(1e9+7)，这么做就错了，这道题有一个循环节的问题，看来这种嵌套的递推式取mod是存在循环节的，以后要注意下。

计算循环节的代码（貌似方法叫做弗洛伊德判圈法？）：

 #include <cstdio>

 #include <iostream>

 using namespace std;

 #define LL __int64

 LL mod=1e9+;

 int main()

 {

     LL i,a,b,g;

     a=,b=;

     for(i=;;i++)

     {

         g=(*a+b)%mod;

         b=a;

         a=g;

         if(a==&&b==)

         {

             if(i!=mod) {mod=i;}

             else break;

             cout<<i<<endl;

             i=;

         }

     }

     return ;

 }

代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;  

 typedef __int64 int64;

 const int N = ;  

 int64 n;

 struct Matrix{

     int64 mat[N][N];

     int64 MOD;

     Matrix operator*(const Matrix& m)const{

           Matrix tmp;

           tmp.MOD = MOD;

           for(int i =  ; i < N ; i++){

               for(int j =  ; j < N ; j++){

                   tmp.mat[i][j] = ;

                   for(int k = ; k < N ; k++)

                       tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;

                   tmp.mat[i][j] %= MOD;

               }

           }

           return tmp;

     }

 };  

 int64 Pow(Matrix m , int64 x , int64 MOD){

     if(x <= ) return x;

     Matrix ans;

     ans.MOD = m.MOD = MOD;

     ans.mat[][] = ans.mat[][] = ;

     ans.mat[][] = ans.mat[][] = ;

     x--;

     while(x){

         if(x%)

             ans = ans*m;

         x /= ;

         m = m*m;

     }

     return ans.mat[][]%MOD;

 }  

 // 暴力找到循环节

 int64 getLoop(int64 MOD){

     int64 pre1 = ;

     int64 pre2 = ;

     for(int64 i =  ; ; i++){

         int64 x = *pre1%MOD+pre2%MOD;

         x %= MOD;

         // update

         pre2 = pre1;

         pre1 = x;

         int64 y = *pre1%MOD+pre2%MOD;

         if(x ==  && y == ){

             return i;

         }

     }

 }  

 int main(){

     int64 L1 = 1e9+;

     int64 L2 = ;

     int64 L3 = ;

     Matrix m;

     m.mat[][] = ; m.mat[][] = ;

     m.mat[][] = ; m.mat[][] = ;

     while(scanf("%I64d" , &n) != EOF){

          int64 x = Pow(m , n , L3);

          int64 y = Pow(m , x , L2);

          int64 ans = Pow(m , y , L1);

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

     }

     return ;

 }

巴特西

HDU4291—A Short problem

最新文章

热门文章