前言

多米诺骨牌的棋盘覆盖问题是一类经典的数学/算法问题。本文讨论添加了免分割线约束条件的多米诺骨牌覆盖问题。

问题描述

多米诺骨牌是 2 × 1 或 1 × 2 的矩形。
考虑用多米诺骨牌覆盖 m × n棋盘，如果无法通过一条不穿过任何骨牌内部的直线，将一种覆盖方案分割成两个部分，那么这种覆盖方案被称为是稳定的。

[补集交形式的容斥原理](https://zh.wikipedia.org/wiki/%E6%8E%92%E5%AE%B9%E5%8E%9F%E7%90%86)

不考虑分割线覆盖方案称为完美覆盖。完美覆盖的计数问题可以使用动态规划求解。

假设已经求出了 i × j 棋盘的完美覆盖数（P_ij）。我们对列运用容斥原理。容斥原理中的A_i表示被i条竖直分割线分割的无横向分割线的覆盖方案；S表示所有无横向分割线的覆盖方案。为了叙述方便，我们称若干个A_i的交称为竖直分割方案。根据容斥原理，我们需要计算每种竖直分割方案下的无横向分割线的覆盖数（R）。我们使用按行（r）递推的方式求解R, 其中R_i表示 i × n棋盘的无横向分割线的覆盖数, 所以R=R_m。为了求解R_i，我们定义一个竖直分割方案下 i × n棋盘的完美覆盖数为SP_i，SP_i的值等于被竖直分割线切分的所有小棋盘完美覆盖数的乘积。假设竖直方案将棋盘切分为3个小棋盘（ i × a, i × b, i × c），其中a+b+c=n。则SP_i = P_ia × P_ib × P_ic. 根据上述定义，R_i的递推公式如下：

1. r = 1, R₁ = SP₁
2. r = k, R_k = SP_k - R₁ × SP_k-1 - R₂ × SP_k-2 - … - R_k-1 × SP₁

递推原理是将SP_k按照位置最高的横向分割线（rc）将覆盖方案分为不相交的k类。每条rc将棋盘分为上下两部分，上部分无横向分割线，下部分允许有横向分割线。假设上部分有l行，则该类的覆盖方案数为R_l × SP_k-l

代码如下（含完美覆盖）：

#include<iostream>
using namespace std;

#define LL long long
#define N 16
LL P[N + 1][N + 1];
LL pc[N + 1][N + 1][1 << N];
LL mod = 1000000007;

pair<LL, LL> p(LL x, LL y, LL i, LL col) {
    if (y > i) return make_pair(x, y - i);
    else return make_pair(x - 1, col);
}

void initP(LL col) {
    LL stateNum = 1 << col;
    for (LL j = 1; j <= col; j++) {
        pc[0][j][stateNum - 1] = 1;
    }
    for (LL i = 1; i <= N; i++) {
        for (LL j = 1; j <= col; j++) {
            LL b = 1 << (j - 1);
            for (LL k = 0; k < stateNum; k++) {
                auto pre = p(i, j, 1, col);
                pc[i][j][k] = pc[pre.first][pre.second][k ^ b];
                LL b2 = 3 << (j - 2);
                if (j > 1 && (b2 & k) == b2) {
                    auto pre1 = p(i, j, 2, col);
                    pc[i][j][k] = (pc[i][j][k] + pc[pre1.first][pre1.second][k]) % mod;
                }
            }
        }
        P[i][col] = pc[i][col][stateNum - 1];
    }
}

void initP() {
    for (LL j = 1; j <= N; j++) {
        initP(j);
    }
}

void getSection(LL state, LL sec[], LL &l, LL y) {
    LL start = 0;
    for (LL j = 1; j < y; j++) {
        if (state & (1 << (j - 1))) {
            sec[l++] = j - start;
            start = j;
        }
    }
    sec[l++] = y - start;
}

int main() {
    initP();
    LL x, y;
    while (cin >> x >> y) {
        LL stateNum = 1 << (y - 1);
        LL ans = 0;
        for (LL i = 0; i < stateNum; i++) {
            LL section[N];
            LL sectionLength = 0;
            LL R[N + 1];
            LL SP[N + 1];
            getSection(i, section, sectionLength, y);
            for (LL r = 1; r <= x; r++) {
                SP[r] = 1;
                for (LL j = 0; j < sectionLength; j++)
                    SP[r] = SP[r] * P[r][section[j]] % mod;
            }
            for (LL r = 1; r <= x; r++) {
                R[r] = SP[r];
                for (LL l = 1; l < r; l++) {
                    R[r] = (R[r] - R[l] * SP[r - l]) % mod;
                }
            }
            if (sectionLength % 2 == 0)
                ans = (ans - R[x]) % mod;
            else
                ans = (ans + R[x]) % mod;
        }
        cout << (ans + mod) % mod << endl;
    }
    return 0;
}