AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
魔仙哥
,
2024-10-11 12:48:24
,
所有人可见
,
阅读 1
/*
f[i][j]表示第i行状态为j的总方案数
1表示竖放的第一个方格,0表示其他情况
初始化f[0][0] = 1
枚举当前行状态j,上一行状态k
j和k没有冲突当且仅当
1) j和k没有共同的1 -- (j&k)==0
2) j和k共同的0的数量为偶数(即当前行和上一行均横放木块)
转移 f[i][j] += f[i-1][k]
答案 f[n][0]
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define F(i,a,b) for(int i=a;i<=b;i++)
const int N = 12,M = 1<<11;
LL f[N][M];
bool st[M];
int n,m;
int main()
{
while(cin>>n>>m,n)
{
F(i,0,n) F(j,0,(1<<m)-1) f[i][j] = 0;
F(i,0,(1<<m)-1)
{
st[i] = 1;
bool f = 0;
F(j,0,m-1)
{
if(!(i>>j&1)) f ^= 1;
else if(f) {st[i] = 0; break;}
}
if(f) st[i] = 0;
}
f[0][0] = 1;
F(i,1,n)
F(j,0,(1<<m)-1)
F(k,0,(1<<m)-1)
if(!(j&k) && st[j|k]) f[i][j] += f[i-1][k];
cout << f[n][0] << '\n';
}
return 0;
}