AcWing 327. 玉米田 滚动数组优化
原题链接
简单
作者:
Snrise
,
2024-04-06 14:48:33
,
所有人可见
,
阅读 1
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 15;
const int M = 1 << N;
const int MOD = 1e8;
int f[2][M];
int g[N];
int st[M], cnt;
int n, m;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int x;
cin >> x;
g[i] = (g[i] << 1) + x;
}
}
for (int i = 0; i < 1 << m; i++)
{
if (!(i & (i >> 1)))
{
st[cnt++] = i;
}
}
f[0][0] = 1;
for (int i = 1; i <= n + 1; i++)
{
for (int j = 0; j < cnt; j++)
{
f[i & 1][j] = 0;
for (int k = 0; k < cnt; k++)
{
if (!(st[j] & st[k]) && (g[i] & st[j]) == st[j])
{
f[i & 1][j] = (f[i & 1][j] + f[(i - 1) & 1][k]) % MOD;
}
}
}
}
cout << f[(n + 1) & 1][0] << endl;
return 0;
}