AcWing 327. 玉米田
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 14, M = 1 << N, mod = 1e8;
int n, m;
int g[N][N];
int f[N][M]; // 前 i - 1 行已经摆好 且第 i 行状态为 j 的方案数
vector<int> state;
vector<int> match[M];
bool check(int x) { // 判断 x 的二进制表示中是否有连续的 1
return x & (x >> 1);
}
bool judge(int i, int j) { // 判断状态 j 是否满足第 i 行
for (int k = 0; k < m; k++)
if (j >> k & 1 && g[i][k + 1] == 0) return false;
return true;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &g[i][j]);
for (int i = 0; i < 1 << m; i++)
if (!check(i)) state.push_back(i);
for (auto x : state)
for (auto y : state)
if (!(x & y)) match[x].push_back(y);
for (int i = 0; i < 1 << m; i++) f[0][i] = 1;
for (int i = 1; i <= n + 1; i++)
for (auto j : state) // 第 i 行的状态
if (judge(i, j))
for (auto a : match[j]) // 第 i - 1 行的状态
if (judge(i - 1, a))
f[i][j] = ((ll)f[i][j] + f[i - 1][a]) % mod;
printf("%d", f[n + 1][0]);
return 0;
}