A - Mondriaan's Dream

求用 \(1\times 2\) 的小矩形填满 \(n\times m\) 的矩形的方案数

sol

数据范围超级小，考虑状压

记录 \(st_i\) 表示 \(i\) 这个二进制状态下的连续 \(0\) 长度是否存在奇数

设 \(dp_{i,j}\) 表示到第 \(i\) 列，且在 \(j\) 中 \(1\) 的位置和 \(i+1\) 列放了横的小方块

然后转移见代码

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int N=13,L=1<<12;
int dp[N][L];
bool st[L];
int n,m;
void init(){
    for(int i=0;i<(1<<n);i++){
        int cnt=0;
        st[i]=1;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                if(cnt&1) break;
                cnt=0;
            }
            else cnt++;
        }
        if(cnt&1) st[i]=0;
        for(int j=1;j<=m;j++) dp[j][i]=0;
    }
}

signed main(){
    while(1){
        cin>>n>>m;
        if(n*m%2==1){
            cout<<0<<"\n";
            continue;
        }
        if(n==0 and m==0) return 0;
        init();
        dp[0][0]=1; 
        for(int i=1;i<=m;i++){
            for(int j=0;j<(1<<n);j++){
                for(int k=0;k<(1<<n);k++){
                    if((j&k) or !st[j|k]) continue;
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
        cout<<dp[m][0]<<"\n";
    }
}