昨天看到名为“矩阵也疯狂”的帖子，老帖了，不过都是很有意思、很经典的题目。其中的第四题是说一个3*n的棋盘用1*2的棋子覆盖，求有多少种覆盖方法，结果模m，其中m、n < 2 ^ 32。
　　不考虑数据范围，一个O(n^2)的dp很容易想到，设f[n]是所求答案，n是奇数结果为0，否则有：
　　　　f[n] = f[n-2] * 3 + f[n-4] * 2 + f[n-6] * 2 + ...
　　一个2 * 3的棋盘有3种摆法，一个4*3的棋盘需要相互交错的摆放，因此有2种摆法，其余依次类推。
　　但是这个递推方程对于这样的数据量肯定是无法接受的。将方程进行化简：
　　　　f[n] = f[n-2] * 3 + (3 * f[n-4] + f[n-6] * 2 + ...) - f[n-4]
　　　　　　 = f[n-2] * 3 + f[n-2] - f[n-4]
　　　　　　 = 4 * f[n-2] - f[n-4]
　　这样就转化成了线性递推方程，可以用矩阵来做了。
　　话说这个题目我在HOJ上做的时候因为数据小就直接O(n^2)了，看来对于一个题目仔细思考、发散思维还是很重要的。
　　既然3*n的可以做，那么4*n应该也可以。后来发现居然还真有这个题：POJ 3420。4*n的递推方程为：
　　　　f[n] = f[n-1] + 4 * f[n-2] + 2 * f[n-3] + 3 * f[n-4] + 2 * f[n-5] + 3 * f[n-6] + ...
　　　　　　 = 5 * f[n-2] + 6 * f[n-3] + 5 * f[n-4] + 5 * f[n-5] + ...
　　　　　　 = 5 * f[n-2] + (5 * f[n-3] + 6 * f[n-4] + 5 * f[n-5] + ...) + f[n-3] - f[n-4]
　　　　　　 = 5 * f[n-2] + f[n-1] + f[n-3] - f[n-4]
　　后面的做法就一样了，算法复杂度(4 ^ 3 * log n)。