总结：满足下面这句话的条件，都可以考虑矩阵乘法+快速幂——把一个向量v变成另一个向量v'，并且v'的每一个分量都是v的各个分量的线性组合。
1、UVa 10870, Recurrences
题意：给出递推关系f(n) = a1*f(n-1) + a2*f(n-2)....ad*f(n-d)，给出d, n, m, a1, a2, ...ad, f(1), f(2)...f(n-d)，求f(n) % m。
解法：矩阵乘法+快速幂。这是我第一次做矩阵乘法的题，由于是专题训练，一上来就构造成f(n) = G * F(n-1)，只需要G = [a1, a2,...ad]，F(n-1) = [f(n-1), f(n-2),...f(n-d)]T即可。
但是，这样构造显然是不对的，我们要构造出的灯式形势应该是这样的(矩阵)F(n) = (d*d的矩阵)G * (矩阵)F(n-1)，只有这样的形式(G为d*d)，才能使用矩阵乘法快速幂。
所以，F(n) = [f(n-d), f(n-d+1),...f(n-1)]T，
G = [0 1 ]
[ 0 1 ]
[... ... ]
[ 0 1]
[ad a(d-1).... a2 a1] (d*d的矩阵)
构造出来，这道题便得以解决。
tag:math, matrix
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-09-10 21:16 4 * File Name: math-UVa-10870.cpp 5 */ 6 #include7 #include 8 #include 9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 #define out(x) cout<<#x<<":"<<(x)< 0){51 if (num & 1) 52 mtx_mul (ret, A, n);53 num >>= 1;54 mtx_mul (A, A, n);55 }56 57 for (int i = 0; i < n; ++ i)58 for (int j = 0; j < n; ++ j)59 A[i][j] = ret[i][j];60 }61 62 int gao (int m, int n)63 {64 matrix A;65 mtx_init (A, n);66 67 mtx_pow (A, m-n, n); 68 int ret = 0;69 for (int i = 0; i < n; ++ i)70 ret = (((A[n-1][i] * f[i+1]) % mod) + ret) % mod;71 if (ret < 0) ret += mod;72 return ret;73 }74 75 int main()76 {77 int n, m; 78 while (scanf ("%d%d%d", &n, &m, &mod) != EOF && n){79 for (int i = 1; i <= n; ++ i){80 scanf ("%d", &a[i]);81 a[i] %= mod;82 }83 for (int i = 1; i <= n; ++ i){84 scanf ("%d", &f[i]);85 f[i] %= mod;86 }87 88 if (m <= n) printf ("%d\n", f[m]);89 else printf ("%d\n", gao (m, n));90 }91 return 0;92 }
2、NEERC 2006, LA 3704, Cellular Automaton
题意：一个环上有n个点，标号依次为0,1...n-1。每次操作后，每个点的值都将变为，与它距离小于等于d的所有点在操作之前的值之和mod m的值。给定n, m, d, k和n个格子各自的值，求经过k次操作之后每个格子的值。
解法：
tag:math, circulant matrix,
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-09-13 12:59 4 * File Name: math-NEERC2006-LA3704.cpp 5 */ 6 #include7 #include 8 #include 9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 14 const int N = 500;15 16 typedef long long int64;17 typedef int64 matrix[N+5];18 19 int n, mod, d, k;20 int64 a[N+5];21 int64 A[N+5];22 23 void mtx_mul(matrix& A, matrix B)24 {25 matrix ret;26 CLR (ret);27 for (int i = 0; i < n; ++ i)28 for (int j = 0, pos = i; j < n; ++ j, pos=(pos-1+n)%n)29 ret[i] = ((A[j] * B[pos]) % mod + ret[i]) % mod;30 31 for (int i = 0; i < n; ++ i)32 A[i] = ret[i];33 }34 35 void mtx_pow(matrix& A, int num)36 {37 if (num == 1) return;38 39 matrix ret;40 for (int i = 0; i < n; ++ i)41 ret[i] = A[i];42 -- num;43 44 while (num > 0){45 if (num & 1) mtx_mul (ret, A);46 num >>= 1;47 mtx_mul (A, A);48 }49 50 for (int i = 0; i < n; ++ i)51 A[i] = ret[i];52 }53 54 void gao()55 {56 CLR (A);57 int pos1 = 0, pos2 = 0;58 int cnt = 0;59 while (cnt <= d){60 A[pos1] = 1; A[pos2] = 1;61 62 ++ cnt;63 pos1 = (pos1+1) % n;64 pos2 = (pos2-1+n) % n;65 }66 67 mtx_pow(A, k);68 69 for (int i = 0; i < n; ++ i){70 int64 x = 0;71 for (int j = 0; j < n; ++ j)72 x = ((A[(j-i+n)%n]*a[j]) % mod + x) % mod;73 74 printf ("%lld", x);75 if (i != n-1) printf (" ");76 }77 printf ("\n");78 }79 80 int main()81 {82 while (scanf ("%d", &n) != EOF){ 83 scanf ("%d%d%d", &mod, &d, &k);84 for (int i = 0; i < n; ++ i)85 scanf ("%lld", &a[i]);86 87 gao ();88 }89 return 0;90 }
3、POJ 3070 Fibonacci
题意：对于Fibonacci数列，“0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …”，(F0 = 0)可以用矩阵的方法求得Fn。给n，求Fn。
解法：本来，如果直接说给n求Fn，这道题还是很有价值的。但是题目不仅仅是直接说了用矩阵求，甚至直接将给出如下图片：
这道题就直接按照这个图片写就好了.....
Ps：用矩阵求类似问题的构造方法，还有就是刘汝佳书上写的那种构造方法，那个是通用的。即本篇文章第一题。
tag:math, matrix, good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-10-14 15:42 4 * File Name: math-POJ-3070.cpp 5 */ 6 #include7 #include 8 #include 9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 const int mod = 10000;14 typedef int matrix[10][10];15 16 void mtx_mul(matrix& A, matrix B)17 {18 matrix ret; CLR (ret);19 for (int i = 0; i < 2; ++ i)20 for (int j = 0; j < 2; ++ j){21 ret[i][j] = 0;22 for (int k = 0; k < 2; ++ k)23 ret[i][j] = (A[i][k] * B[k][j] + ret[i][j]) % mod;24 }25 26 for (int i = 0; i < 2; ++ i)27 for (int j = 0; j < 2; ++ j)28 A[i][j] = ret[i][j];29 }30 31 void mtx_pow(matrix& A, int n)32 {33 -- n;34 matrix ret; CLR (ret);35 for (int i = 0; i < 2; ++ i)36 for (int j = 0; j < 2; ++ j)37 ret[i][j] = A[i][j];38 while (n > 0){39 if (n & 1) mtx_mul(ret, A);40 n >>= 1;41 mtx_mul(A, A);42 }43 for (int i = 0; i < 2; ++ i)44 for (int j = 0; j < 2; ++ j)45 A[i][j] = ret[i][j];46 }47 48 int main()49 {50 int n;51 while (scanf ("%d", &n) != EOF && n != -1){52 matrix A; CLR (A);53 A[0][0] = 1; A[0][1] = 1; A[1][0] = 1;54 if (n < 4){55 if (!n) printf ("0\n");56 if (n == 1 || n == 2) printf ("1\n");57 if (n == 3) printf ("2\n");58 continue;59 }60 mtx_pow(A, n);61 printf ("%d\n", A[0][1] % mod); 62 }63 return 0;64 }