2016弱校联盟十一专场10.5 F Fibonacci of Fibonacci（矩阵快速幂 +

2019-04-14 20:19发布

站内文章 / 模拟电子
10861 0 1164
class="markdown_views prism-atom-one-light"> 传送门
题目描述 题目大意： 给定一个斐波那契数列 Fn,让你求 FFn 解题思路： 首先我们将 Fn 的循环节找到， 然后套一下矩阵快速幂模的是MOD1，那么底数就变成了比较小的一个数（不至于太大），然后在套一下矩阵快速幂这次是模MOD。 My Code： #include #include #include #include #include #include using namespace std; typedef long long LL; const int MAXN = 2; const LL MOD = 20160519LL; const LL MOD1 = 26880696LL;///循环节 LL fib[MOD1+5], fib1[MOD1+5]; void Init(){ fib[0] = 0, fib[1] = 1; for(int i=2; i5; i++) fib[i] = (fib[i-1] + fib[i-2])% MOD; } typedef struct { LL mat[MAXN][MAXN]; } Matrix; ///求得的矩阵 Matrix p = {1, 1, 1, 0, }; ///单位矩阵 Matrix I = {1, 0, 0, 1, }; ///矩阵乘法 Matrix Mul_Matrix(Matrix a, Matrix b, LL MOD) { Matrix c; for(int i=0; ifor(int j=0; j0; for(int k=0; kreturn c; } ///矩阵的快速幂 Matrix quick_Mod_Matrix(LL m, LL MOD) { Matrix ans = I, b = p; while(m) { if(m & 1) ans = Mul_Matrix(ans, b, MOD); m>>=1; b = Mul_Matrix(b, b, MOD); } return ans; } ///普通的快速幂 LL quick_Mod(LL a, LL b, LL MOD) { LL ans = 1; while(b) { if(b & 1) ans = (ans * a) % MOD; b>>=1; a = (a * a) % MOD; } return ans; } int main() { /**找循环节**/ /**Init(); for(int i=3; i int T; scanf("%d",&T); while(T--){ LL n; scanf("%lld",&n); Matrix tmp = quick_Mod_Matrix(n-1, MOD1); LL tp = tmp.mat[0][0]; tmp = quick_Mod_Matrix(tp-1, MOD); LL ans = tmp.mat[0][0]; printf("%lld ",ans); } return 0; }

热门文章