201409-5 拼图

思路：

这道题就是典型的状态压缩DP+矩阵快速幂+DFS。这里主要学的思想是如果后一个状态推前一个状态的推法是固定的，那么就是一个固定的递推方程，所以可以用矩阵加快速幂来加速。而DFS是求最初的转移矩阵的好方法，因为我们需要直到第i列是什么样子，i列之前才可以填满，而且对应的下一列j的样子才是有效的。所以这里直接暴力dfs，总的来说还是很难的。

代码：

#include 
#include 
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 130;
ll n;
int m;
int w[N][N];
int res[N][N];
void dfs(int x, int y, int u){
    if(u == m){
        w[x][y]++;
        return;
    }
    if(x >> u & 1){
        dfs(x, y, u + 1);
    }else{
        if(u && !(y >> u & 1) && !(y >> (u - 1) & 1)){
            dfs(x, y + (1 << u) + (1 << (u - 1)), u + 1);
        }
        if(u + 1 < m && !(y >> u & 1) && !(y >> (u + 1) & 1)){
            dfs(x, y + (1 << u) + (1 << u + 1), u + 1);
        }
        if(u + 1 < m && !(x >> (u + 1) & 1)){
            if(!(y >> u & 1))dfs(x, y + (1 << u), u + 2);
            if(!(y >> (u + 1) & 1))dfs(x, y + (1 << (u + 1)), u + 2);
        }
    }
}
void mul(int c[][N], int a[][N], int b[][N])
{
    static int tmp[N][N];
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i < 1 << m; i ++ )
        for (int j = 0; j < 1 << m; j ++ )
            for (int k = 0; k < 1 << m; k ++ )
                tmp[i][j] = (tmp[i][j] + (ll)a[i][k] * b[k][j]) % mod;
    memcpy(c, tmp, sizeof tmp);
}
int main(){
    cin>>n>>m;
    for(int i = 0;i<1<){
        dfs(i, 0, 0);
    }
    int res[N][N] = {0};
    res[0][(1 << m) - 1] = 1;
    while (n)
    {
        if (n & 1) mul(res, res, w);
        mul(w, w, w);
        n >>= 1;
    }
    cout << res[0][(1 << m) - 1] << endl;
    return 0;
}