矩阵题目总结
题目来源参考了：http://blog.csdn.net/a601025382s/article/details/10251613
简单矩阵：
HDU 1575：http://acm.hdu.edu.cn/showproblem.php?pid=1575
题意：给定矩阵A， 求Tr(A^k) % 9973。 其中Tr为矩阵的迹
代码
ZOJ 3690：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973
题意：N个人站在一排，每个人可以从[1,m]中选一个号码，规定两个相邻的如果选择的数字相同，该数字必须大于k。问有多少种方案
思路：F[n][0] = max(k - 1, 0) * F[n - 1][0] + k * F[n-1][1]
F[n][1] = (m - k) * F[n - 1][0] + (m - k) * F[n - 1][1] //其中F[i][j] 表示到i个人时，选择的j状态，j一共有两种状态，0表示选的数字小于等于k，1表示数字大于k
代码：http://paste.ubuntu.com/8105982/
常系数线性齐次递推
HDU 1005： http://acm.hdu.edu.cn/showproblem.php?pid=1005
题意：f[n] = (A * f[n - 1] + B * f[n - 2]) % mod, f[1] = f[2] = 1, 给定A,B,n，求f[n]。 代码
HDU 1757：http://acm.hdu.edu.cn/showproblem.php?pid=1757
题意：If x < 10 f(x) = x. If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10) And
ai(0<=i<=9) can only be 0 or 1 .现在给你k和m，求f(k) % m。解题报告
逆矩阵：
POJ 1166： http://poj.org/problem?id=1166
题意：9只钟表排成3 * 3的矩阵，每个钟只能指向上下左右四个位置，现在给你9种作用方式，每种可以使一些钟表的指针右转90度。现在使用这九种方式，使得所有钟表都朝上。求总作用次数最少的策略
思路：这道题之前用二进制枚举做过，每种作用方式四次一循环，所以暴力为：1 << 18。但如果作用方式变多一些，就不能这么做了。
可以采用逆矩阵来解这道题：
具体看下面的链接：传送门（讲的非常详细）
代码：http://paste.ubuntu.com/7862915/
矩阵 + dp
POJ 3734：http://poj.org/problem?id=3734
题意：有一排砖，数量为N。现要将砖全部染上色，有红、蓝、绿、黄四种颜色。要求被染成红色和绿色的砖块数量必须为偶数，问一共有多少种染色方案。（由于答案较大，模10007）解题报告
POJ 3420： http://poj.org/problem?id=3420
题意：有一个 4 * N (1 ≤ N ≤ 10^9) 的矩形，用1 * 2 的木块去铺满它，问有多少种方法。答案可能很大，对 M 取模。
思路：这道题目的难点在于dp，如何找到状态转移是突破点， （POJ 2411 的题解，有详细的解释）。可以写成一个16 * 16 的矩阵，然后再用矩阵快速幂即可。