AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
liuwj9923
,
2025-04-01 22:09:17
·吉林
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 12,M = 1<<N;
ll f[N][M];
bool st[M];
vector<int> state[M];
int main(){
int n,m;
while(cin>>n>>m,n||m){
for(int i = 0;i<1<<n;i++){
int cnt = 0;
bool flag = true;
for(int j = 0;j<n;j++){
if((i>>j)&1){
if(cnt%2==1) {
flag = false;
break;
}
cnt = 0;
}else cnt++;
}
if(cnt%2==1) flag =false;
st[i] = flag;
}
for(int j = 0;j<1<<n;j++){
state[j].clear();
for(int k = 0;k<1<<n;k++){
if((j&k)==0&&st[j|k]) state[j].push_back(k);
}
}
memset(f,0,sizeof f);
f[0][0] = 1;
for(int i =1;i<=m;i++){
for(int j = 0;j<1<<n;j++){
for(auto w :state[j]) f[i][j] += f[i-1][w];
}
}
cout<<f[m][0]<<endl;
}
return 0;
}