多米诺骨牌
题目链接：luogu P2595
题目大意
给你一个 n*m 的矩阵，你可以横竖放 1*2 的木块。
问你有多少种方法，使得每相邻的两行之间必定有横跨的木块，每相邻的两列之间必有横跨的木块。
不是一定要全部放满木块。
思路
首先看到这种题不难想到插头 DP。
但是你发现它那个要求很烦。
那你先不要管他，不难预处理出 (g_{x1,x2,y1,y2}) 为区间 ([x1,y1][x2,y2]) 随便放的方案数。
（看似是 (n^3m^22^m)，但我们其实可以在跑的过程中压掉一维，变成 (n^2m^22^m)）
然后我们考虑去搞它的要求。
那发现还是不会搞，那我们考虑反过来，求全部的减去有不横跨的。
那不横跨的其实很简单，你把两个 (g) 拼在一起，得到的方案数是两个相乘，就可以保证拼接的地方不可能有横跨了。
那不难想到可以枚举分割的状态，但是你两个维度搞在一起还是会超时。
然后你就考虑一个维度直接暴力枚举状态，然后另一个维度用 DP 来搞。
怎么 DP 呢，大概是设 (F_i) 为前 (i) 部分分割好了的方案数，然后就 (n^2) 转移。（然后转移的时候注意原来只有一段的情况，然后也容斥一下）
然后这么搞就好了。
我的代码常数大，要卡一卡时间，然后一开始预处理 (g) 的插头 DP 其实还可以滚动数组，但我没用。
（我直接开 O2 了）
代码
#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#define mo 19901013
#define rr register
#define ll long long
using namespace std;
int n, m, nxt, a[16], xx, yy, nn, mm;
int g[16][16][16][16], f[16][16][70001], ans;
int sum, F[16];
bool cn[16][16];
char c;
void slove(int x1, int y1, int y2) {//求出一个区间任意放的方案
nn = n - x1 + 1;
mm = y2 - y1 + 1;
f[0][0][(1 << mm) - 1] = 1;
for (int x = 0; x < nn; x++)
for (int y = 0; y < mm; y++) {
if (y == mm - 1) xx = x + 1, yy = 0;
else xx = x, yy = y + 1;
for (rr int k = 0; k < (1 << mm); k++) {
if (!cn[x + x1][y + y1]) f[xx][yy][k | (1 << y)] = (f[xx][yy][k | (1 << y)] + f[x][y][k]) % mo;
else {
nxt = k;
if ((nxt >> y) & 1) nxt ^= (1 << y);
f[xx][yy][nxt] = (f[xx][yy][nxt] + f[x][y][k]) % mo;
if (!((k >> y) & 1)) f[xx][yy][k | (1 << y)] = (f[xx][yy][k | (1 << y)] + f[x][y][k]) % mo;
if (y > 0 && !((k >> (y - 1)) & 1))
f[xx][yy][k | (1 << y) | (1 << (y - 1))] = (f[xx][yy][k | (1 << y) | (1 << (y - 1))] + f[x][y][k]) % mo;
}
}
}
for (int i = x1; i <= n; i++)
for (rr int k = 0; k < (1 << mm); k++)
g[x1][i][y1][y2] = (g[x1][i][y1][y2] + f[i - x1 + 1][0][k]) % mo;
for (int i = 0; i <= nn; i++)
for (int j = 0; j < mm; j++)
for (rr int k = 0; k < (1 << mm); k++)
f[i][j][k] = 0;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
c = getchar();
while (c != 'x' && c != '.') c = getchar();
if (c == '.') cn[i][j] = 1;
else cn[i][j] = 0;
}
for (int x1 = 1; x1 <= n; x1++)
for (int y1 = 1; y1 <= m; y1++)
for (int y2 = y1; y2 <= m; y2++) {
slove(x1, y1, y2);
}
for (int k = 0; k < (1 << (m - 1)); k++) {
memset(F, 0, sizeof(F));
a[0] = 0;
a[++a[0]] = 0;//搞出这个状态对应的每个分割位
for (int i = 0; i < m - 1; i++)
if ((k >> i) & 1) a[++a[0]] = i + 1;
a[++a[0]] = m;
for (int i = 1; i <= n; i++) {//另外一个维度用 n^2 DP
for (int j = 1; j <= i; j++) {
sum = 1;
for (int x = 2; x <= a[0]; x++) {
sum = (1ll * sum * g[j][i][a[x - 1] + 1][a[x]]) % mo;
}
if (j == 1) F[i] = sum;//容斥
else F[i] = (F[i] - (1ll * sum * F[j - 1]) % mo + mo) % mo;
}
}
if (a[0] & 1) ans = (ans - F[n] + mo) % mo;
else ans = (ans + F[n]) % mo;//容斥
}
printf("%d
", ans);
return 0;
}