这道题， 给我的最大的知识点就是对于去模运算，一定可以找到循环节，这题只不过是嵌套了两层，可以分别找到循环节。关于这题如何找循环节的，直接暴力，网上也有很多。
找到循环节之后，另一个知识点就是对于线性关系可以使用矩阵快速幂来加速。
附上代码：
1 /************************************************************************* 2 > File Name: 4292.cpp 3 > Author: Stomach_ache 4 > Mail: 1179998621@qq.com 5 > Created Time: 2014年04月20日 星期日 22时06分59秒 6 > Propose: 7 ************************************************************************/ 8 #include <iostream> 9 #include <cmath> 10 #include <algorithm> 11 #include <cstring> 12 #include <string> 13 #include <cstdio> 14 #include <fstream> 15 16 using namespace std; 17 18 #define MOD1 (1000000007) 19 #define MOD2 (222222224) 20 #define MOD3 (183120) 21 22 typedef long long LL; 23 24 struct Matrix { 25 LL a[2][2]; 26 //Matrix(int m):n(m){memset(a, 0, sizeof(a));} 27 inline Matrix multiply(Matrix& y, LL mod) { 28 Matrix ret; 29 for (LL i = 0; i < 2; i++) { 30 for (LL j = 0; j < 2; j++) { 31 LL tmp = 0; 32 for (LL k = 0; k < 2; k++) { 33 tmp = (tmp+a[i][k]*y.a[k][j])%mod; 34 //ret.a[i][j] = (ret.a[i][j]+tmp)%mod; 35 } 36 ret.a[i][j] = tmp; 37 } 38 } 39 40 return ret; 41 } 42 }; 43 44 Matrix power_mod(Matrix x, LL y, LL mod) { 45 Matrix ans; 46 ans.a[0][0] = ans.a[1][1] = 1; 47 ans.a[0][1] = ans.a[1][0] = 0; 48 while (y) { 49 if (y % 2) { 50 ans = ans.multiply(x, mod); 51 } 52 x = x.multiply(x, mod); 53 y /= 2; 54 } 55 56 return ans; 57 } 58 59 int main(void) { 60 Matrix A; 61 A.a[0][0] = 0; 62 A.a[1][0] = 1; 63 A.a[0][1] = 1; 64 A.a[1][1] = 3; 65 LL n; 66 while (cin >> n) { 67 if (n == 0 || n == 1) { 68 cout << n << endl; 69 continue; 70 } 71 Matrix tmp1 = power_mod(A, n-1, MOD3); 72 n = tmp1.a[1][1]; 73 if (n != 0 && n != 1) { 74 tmp1 = power_mod(A, n-1, MOD2); 75 n = tmp1.a[1][1]; 76 } 77 if (n != 0 && n != 1) { 78 tmp1 = power_mod(A, n-1, MOD1); 79 n = tmp1.a[1][1]; 80 } 81 cout << n << endl; 82 } 83 return 0; 84 }