骨牌覆盖问题
骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个长条形的棋盘，然后用 1X2 的骨牌去覆盖整个棋盘，那么对于这个棋盘总共有多少种不同的覆盖方法？2xN的棋盘
我们考虑在已经放置了部分骨牌(灰色)的情况下，下一步可以如何放置新的骨牌(蓝色)：
最右边的一种情况是不可能发生的，否则会始终多一个格子没有办法放置骨牌。或者说灰色部分的格子数为奇数，不可能通过1x2个骨牌放置出来。
那么通过对上面的观察，我们可以发现： 在任何一个放置方案最后，一定满足前面两种情况。而灰色的部分又正好对应了长度为N-1和N-2时的放置方案。由此，我们可以得到递推公式:f[n] = f[n-1] + f[n-2];
这个公式是不是看上去很眼熟？没错，这正是我们的费波拉契数列。
f[0]=1,f[1]=1,f[2]=2,...
当 N 很小的时候我们可以直接递推得到结果，而当 N 很大的时候，就不是很方便了。对于这种线性递推式我们可以用矩阵来求第 n 项，对于 Fibonacci 数列，我们希望找到一个2x2的矩阵M，使得(a, b) x M = (b, a+b)，其中(a, b)和(b, a+b)都是1x2的矩阵。
显然，只要 M = [0, 1; 1, 1]
所以可得：
这就可以使用快速幂来求
将 k[1]..k[j]划分的好一点
其中(k[1],k[2]...k[j])2表示将n表示成二进制数后每一位的数字。上面这个公式同时满足这样一个性质：
所以:
先计算出所有的{a^1, a^2, a^4 ... a^(2^j)}，因为该数列满足递推公式，时间复杂度为O(logN)
将指数n二进制化，再利用公式将对应的a^j相乘计算出a^n，时间复杂度仍然为O(logN)
则总的时间复杂度为O(logN)#include
using namespace std; const int NUM=1000000007; void cal(long long a[2][2],long long b[2][2]) { long long c[2][2]; c[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%NUM; c[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%NUM; c[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%NUM; c[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%NUM; a[0][0]=c[0][0]; a[0][1]=c[0][1]; a[1][0]=c[1][0]; a[1][1]=c[1][1]; } int main() { long int n; cin>>n; long long r[2][2]={1,0,0,1}; long long a[2][2]={0,1,1,1}; while(n!=0) { if(n&1) cal(r,a); cal(a,a); n>>=1; // cout << n << endl; } cout<
3xN的棋盘
这是对 2xN 的棋盘的扩展，按照相同的思路，找到对应的递推式子
假设我们已经放好了一些骨牌，对于当前最后一列(第i列)骨牌，可能有8种情况, 并将其看做二进制数，则有：
对于正在放置第i行的骨牌，那么会有3种方式，每一种放置方法解释如下，假设当第i行的状态为x，第i-1行的状态为y：
- 第 i 行不放置，则前一行必须有放置的骨牌。x对应二进制位为0，y对应二进制位为1。
- 第 i 行竖放骨牌，则前一行必须为空。x对应二进制位为1，y对应二进制位为0。
- 第 i 行横向骨牌，则前一行必须两个位置均有骨牌，否则会产生空位。x对应二进制位为1，y对应二进制位为1。
其中会有这么个情况：
这种情况看似是从状态 1 变成了状态 0 ，其实是不对的。它不满足我们约定的放置方法，本质是第 i 行的状态 1 变成了第 i 行的状态 7，而实际上我们应该放置的是第 i+1 行。
通过枚举 8 种状态之间的转移，可以得到一个 8x8 的矩阵M
M[i][j] 表示从状态 i 到状态 j 的方案数。
在2xN的骨牌覆盖中，有(0, 1)作为初始向量A，那么在3xN中初始向量A是如何呢？
很显然，第 0 行在我们递推的过程中必须看作状态 7 才合理。故A向量表示为：
{0, 0, 0, 0, 0, 0, 0, 1}
而对于我们寻求的答案，自然也是第n行放置为状态 7 的方案数了。
KxN的棋盘
通过之前的递推的方法，可以知道，对于任意的 K 值，我们每一行拥有的状态数目为 2^K 种
当 K=3 的时候可以手动枚举 8 种状态之间的递推关系
而 k=4 或者更大的时候就不合适了
对于正在放置第i行的骨牌，由之前可知其对应的二进制表示，那么三种方法可以由程序语言：
- 第i行不放置：new_x = x << 1, new_y = (y << 1) + 1; 列数+1
- 第i行竖放骨牌：new_x = (x << 1) + 1, new_y = y << 1; 列数+1
- 第i行横向骨牌：new x = (x << 2) + 3, new_y = (y << 2) + 3; 列数+2
通过迭代去枚举 3 种放置方法，当列数等于 K 的时候，此时的x便可由y转移过来。那么我们可以得到枚举放置的伪代码：
DFS(x, y, col):If col == K d[y][x] = 1 Return ;EndDFS(x << 1, (y << 1) + 1, col + 1);DFS((x << 1) + 1, y << 1, col + 1);If col + 2 <= K DFS( (x << 2) + 3, (y << 2) + 3, col + 2 )End
由此得到对应的矩阵，继续由快速幂求解
在某些题目中有可能会出现，N很小，K很大的情况。比如N=20,K=14这样的情况。
考虑到N很小，我们可以不使用矩阵乘法，而直接采用f[i-1]到f[i]行的递推。时间复杂度也就转化为2^(2k)*N。
但是状态数量为2^14，也就是16384种。若采用转移矩阵，肯定是无法储存的。而实际情况是在转移矩阵中1的数量并不多，所以我们可以考虑存储为(y,x)这样的二元组。在转移过程中只枚举合法的转移即可。
若K再更大一点，比如K=20，产生的状态有可能连开数组存储都很吃力。这个时候我们也可以考虑在计算每一行时，直接通过dfs来进行转移，不储存转移关系。用时间来换取空间。
参考：