题意：求有多少种方案，用多米诺骨牌覆盖一个\(n\times m\)的棋盘，满足任意一对相邻行和列都至少有一个骨牌横跨。对\(10^9+7\)取模。
\(n,m \leq 16\)
首先，这个问题的约束比较复杂，直接dp需要较高的代价记录状态，不能通过本题。
然而，这个问题的约束可以被拆分为多个小约束（某条线被横跨），且小约束可以直接合并。这启发我们使用容斥。
这样，我们的dp计数就简化为了固定几条线不被跨越后任意覆盖。设\(f_k\)为恰有\(k\)条线不被跨越的方案数，\(g_k\)为我们计算出的固定了\(k\)条线后的覆盖方案数。那么，我们有
\[g_k = \sum_{i \geq k} {{i}\choose{k}} f_i
\]
\]
由二项式反演可得
\[f_0 = \sum_{k \geq 0} (-1)^k g_k
\]
\]
剩下的问题就在于计算所有\(g_k\)了。我们不能枚举所有要被跨越的线，但是枚举一维之后，另一维就可以dp了。假设我们已经枚举了列上的线，令\(dp_{i,j}\)表示前\(i\)行有\(j\)条线没有跨越的方案数，暴力转移。通过预处理能做到\(O(n^3)\)。而考虑到状态中的\(j\)至于最后\(-1\)的指数有关，故可以省去。因此这个dp是\(O(n^2)\)的。
时间复杂度\(O(n^2 2^n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 20, MOD = (int)(1e9 + 7), MAX = 16;
int n,m,dp[2][1 << MAX],f[N][N],ans,g[N],rec[N];
typedef long long ll;
void doit(int wd) {
memset(dp,0,sizeof dp);
int p = 1, lim = (1 << wd) - 1;
dp[0][(1 << wd)-1] = 1;
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= wd ; ++ j, p ^= 1) {
memset(dp[p],0,sizeof dp[p]);
for (int s = 0 ; s < (1 << wd) ; ++ s) {
if (((s >> (wd-1))&1) == 0)
(dp[p][(s << 1 | 1) & lim] += dp[p^1][s]) %= MOD;
else {
if ((!(s&1)) && j != 1) (dp[p][(s << 1 | 3) & lim] += dp[p^1][s]) %= MOD;
(dp[p][(s << 1) & lim] += dp[p^1][s]) %= MOD;
}
}
}
f[i][wd] = dp[p^1][lim];
}
}
void prework() {
for (int i = 1 ; i <= m ; ++ i)
doit(i);
}
vector<int> tmp;
int main() {
n = m = 16;
prework();
while (scanf("%d%d",&n,&m) != EOF) {
ans = 0;
for (int s = (1 << m >> 1) ; s < (1 << m) ; ++ s) {
tmp.clear();
int las = 0;
for (int i = 1 ; i <= m ; ++ i)
if ((s >> (i-1))&1) tmp.push_back(i-las), las = i;
for (int i = 1 ; i <= n ; ++ i) {
rec[i] = 1;
for (int j = 0 ; j < (int)tmp.size() ; ++ j)
rec[i] = 1ll * rec[i] * f[i][tmp[j]] % MOD;
}
memset(g,0,sizeof g);
for (int i = 1 ; i <= n ; ++ i) {
g[i] = rec[i];
for (int k = 1 ; k < i ; ++ k)
(g[i] += -1ll * rec[i-k] * g[k] % MOD) %= MOD;
}
if (tmp.size()&1) (ans += g[n]) %= MOD;
else (ans -= g[n]) %= MOD;
}
ans = (ans % MOD + MOD) % MOD;
printf("%d\n",ans);
}
return 0;
}
小结：本题的关键在于想到容斥，以及枚举一维后dp另一维。这两个思路都有较广的适用性，有必要熟练运用。