题目传送:UVA - 10229
思路:就是简单的矩阵快速幂求fibonacci数列,然后注意可能中间结果会爆int,因为2^19有50多万
AC代码:
#include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define INF 0x7fffffff using namespace std; int mp[20]; LL n, m; void init() { mp[0] = 1; for(int i = 1; i <20; i ++) { mp[i] = 2 * mp[i - 1]; } } struct matrix { LL m[2][2]; }; matrix ans; matrix base = {1, 1, 1, 0}; matrix multiply(matrix a, matrix b, LL MOD) { matrix ret; for(int i = 0; i <2; i ++) { for(int j = 0; j <2; j ++) { ret.m[i][j] = 0; for(int k = 0; k <2; k ++) { ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD; } } } return ret; } LL kmod(matrix a, LL n, LL MOD) { matrix ans = {1, 0, 0, 1}; while(n) { if(n & 1) ans = multiply(ans, a, MOD); a = multiply(a, a, MOD); n >>= 1; } return ans.m[0][1]; } int main() { init(); while(cin >> n >> m) { cout < UVA - 10229 - Modular Fibonacci (矩阵快速幂 + fibonacci)
UVA - 10229 - Modular Fibonacci (矩阵快速幂 + fibonacci)