更新时间:2022-08-12 16:38:53
思路: 循环节+矩阵快速幂
分析:
1 题目给定g(n) = 3*g(n-1)+g(n-2) , g(1) = 1 , g(0) = 0 , 要求g(g(g(n)))%10^9+7
2 最初的想法是从里面一层一层的求出g(n),每一次都利用矩阵快速幂。但是发现嵌套的时候只有最外层是%(10^9+7),但是里面两层如果%(10^9+7)的话答案是错的。
那么这里涉及到了循环节,最外层%(10^9+7),肯定有个循环节L1。那么我们可以通过求出的L1找到第二层的循环节为L2,通过第二层的循环节L2找到第三层的循环节L3
3 找循环节我们利用暴力求出即可。然后我们回答最初的思路上,只要做三次的矩阵快速幂,然后把相应要mod上相应的值即可
代码:
/************************************************ * By: chenguolin * * Date: 2013-08-30 * * Address: http://blog.csdn.net/chenguolinblog * ************************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef __int64 int64; const int N = 2; int64 n; struct Matrix{ int64 mat[N][N]; int64 MOD; Matrix operator*(const Matrix& m)const{ Matrix tmp; tmp.MOD = MOD; for(int i = 0 ; i < N ; i++){ for(int j = 0 ; j < N ; j++){ tmp.mat[i][j] = 0; for(int k = 0; 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 <= 1) return x; Matrix ans; ans.MOD = m.MOD = MOD; ans.mat[0][0] = ans.mat[1][1] = 1; ans.mat[1][0] = ans.mat[0][1] = 0; x--; while(x){ if(x%2) ans = ans*m; x /= 2; m = m*m; } return ans.mat[0][0]%MOD; } // 暴力找到循环节 int64 getLoop(int64 MOD){ int64 pre1 = 1; int64 pre2 = 0; for(int64 i = 2 ; ; i++){ int64 x = 3*pre1%MOD+pre2%MOD; x %= MOD; // update pre2 = pre1; pre1 = x; int64 y = 3*pre1%MOD+pre2%MOD; if(x == 0 && y == 1){ return i; } } } int main(){ int64 L1 = 1e9+7; int64 L2 = 222222224; int64 L3 = 183120; Matrix m; m.mat[0][0] = 3; m.mat[1][1] = 0; m.mat[0][1] = 1; m.mat[1][0] = 1; 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 0; }