来源：http://acm.fzu.edu.cn/problem.php?pid=1683        概述：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
理论分析
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
编程分析        （1）要写一个矩阵相乘函数MUL(int a[][N], int b[][N], int c[][N])，其中N为宏定义——#define N 4，代表其为四阶方阵。该函数将矩阵a*b的结果保存在c矩阵。        （2）其次，要为写一个快速幂模函数POW(int b, int P[][N])，参数b代表其次幂数n-2，参数P用来保存最后结果的返回值。        （3）矩阵赋值，可以使用memcpy函数完成。 #include #include using namespace std; #define MOD 2009 #define N 4 const int NUM = sizeof(int)*N*N; void MUL(int a[][N], int b[][N], int c[][N]) { int i, j; for (i = 0; i < N; i++) for (j = 0; j < N; j++) c[i][j] = (a[i][0]*b[0][j] + a[i][1]*b[1][j] + a[i][2]*b[2][j] + a[i][3]*b[3][j]) % MOD; } void POW(int b, int P[][N]) { int A[N][N] = {{1,3,2,7},{0,3,2,7},{0,1},{0,0,1}}, T[N][N]; memset(P, 0, NUM); for (int i = 0; i < N; i++) P[i][i] = 1; while (b) { if (b&1) { MUL(P, A, T); memcpy(P, T, NUM); } b >>= 1; MUL(A, A, T); memcpy(A, T, NUM); } } int main() { int t, T, n, P[N][N], ans; scanf("%d", &T); for (t = 1; t <= T; t++) { scanf("%d", &n); if (n == 0) ans = 1; else if (n == 1) ans = 4; else { POW(n-2, P); ans = (9*P[0][0]+5*P[0][1]+3*P[0][2]+P[0][3]) % MOD; } printf("Case %d: %d ", t, ans); } return 0; }        花絮：写完后太开心，着急着提交，没想到既然会TLE，太伤心了，我觉得我的优化水平只能到如此，这样都TLE，这题我无能为力了。然后才发觉自己n=0和n=1的特殊情况忘记处理。。。改完后，就用281ms AC了。再分析后，我发现我的代码确实还能再优化，就是接下来补充内容讲到的MUL函数。 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 补充：关于MUL函数效率        有些人会写一个Matrix的结构体，然后重载*运算符为矩阵乘法。但我觉得那样写，代码不够精简，直接用数组存储矩阵，然后写这样一个MUL函数也是很方便使用的。        在MUL函数里，矩阵相乘一般是要三层循环的，那样的话，使用c数组前要初始化所有元素为0（可以使用memset函数），像这段代码： void MUL(int a[][N], int b[][N], int c[][N]) { int i, j, k; memset(c, 0, NUM); for (i = 0; i < N; i++) for (j = 0; j < N; j++) { for (k = 0; k < N; k++) { c[i][j] += a[i][k]*b[k][j]; } c[i][j] %= MOD; } }        这样付出的效率代价是很高的，用这个MUL函数求解该题，需要218ms。当矩阵阶数不是特别大时，去掉第三层的k循环，将式子展开赋值，上述题目这样操作仅需109ms，效率提高了一倍。        有时候数值比较大，怕溢出时，则不得不用三层循环的MUL，要注意把代码写成这样： void MUL(int a[][N], int b[][N], int c[][N]) { int i, j, k; memset(c, 0, NUM); for (i = 0; i < N; i++) for (j = 0; j < N; j++) for (k = 0; k < N; k++) { c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD; } }       这时候MOD写在最内层，效率又会下降，这题采用该代码，用时281ms。