蒙德里安的梦想

蒙德里安的梦想

P10975 Mondriaan’s Dream

问题概述

用 1×21×2 和 2×12×1 的多米诺骨牌覆盖 n×m棋盘，求方案数。n,m≤11n,m≤11。

状态定义

f

[

i

]

[

j

]

f[i][j]

f[i][j]：前 ii 行已填满，且第 ii 行有方块伸到第 i+1i+1 行的列状态为 j的方案数。

j是 m位二进制数，第 p位为 1表示第 p列有方块从第 ii 行伸到第 i+1 行。

状态总数 2^m

转移方程

f

[

i

]

[

j

]

=

∑

f

[

i

−

1

]

[

k

]

f[i][j]=∑f[i−1][k]

f[i][j]=∑f[i−1][k]

其中 kk 是第 i−1i−1 行的伸出状态，需满足：

预处理合法性

st[state]s**t[state] 表示状态 statestate 是否合法：所有连续 00（空位）的个数均为偶数。

cpp

bool check(int state, int w) {
int cnt = 0;
for (int i = 0; i < w; i++) {
if (state >> i & 1) {
if (cnt & 1) return false;
cnt = 0;
} else cnt++;
}
return (cnt & 1) == 0;
}

例（m=4m=4）：0(0000)0(0000) 合法，3(0011)3(0011) 合法，5(0101)5(0101) 非法（中间有1个0）。

完整代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N;
long long f[N][M];
bool st[M];
int n, m;

bool check(int state, int w) {
int cnt = 0;
for (int i = 0; i < w; i++) {
if (state >> i & 1) {
if (cnt & 1) return false;
cnt = 0;
} else cnt++;
}
return (cnt & 1) == 0;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

while (cin >> n >> m, n || m) {
memset(f, 0, sizeof f);

for (int i = 0; i < 1 << m; i++)
st[i] = check(i, m);

f[0][0] = 1;

for (int i = 1; i <= n; i++)
for (int j = 0; j < 1 << m; j++)
for (int k = 0; k < 1 << m; k++)
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i – 1][k];

cout << f[n][0] << '\\n';
}
return 0;
}