ABC196 D - Hanjo

ざっと見て自分と同じ解法の人がいなかったので

問題

atcoder.jp

解法

制約が小さいのでbitDPみたいなのが考えられそう．2×1の畳の敷き方が決まれば全体の敷き方も一意に決まるので，以下は2×1の畳を敷いた状態を考える．
dp[bit][j]:2×1の畳をちょうどj枚敷いた時の”敷く順番を考慮した場合の”敷き方
とする．ここでbitは敷き詰められたマスの集合を表す．敷く順番を考慮するというのがミソで，この条件を敷いてやることで遷移が一意に決まる．具体的には以下の通りに書ける（自明な気もするが）．
dp[bit|(1<<i)|(1<<ni)][j+1]+=dp[bit][j]
ここでiとかniというのは畳を敷く時に埋められるマスを表す．あとはこの遷移をぶん回してdpテーブルの各値を求めたあとにsum(dp[bit][A])を求めて，A!で割ってやることで答えが求まる．

提出

atcoder.jp

#include<bits/stdc++.h>
using namespace std;

int main(){
  //input
  int h,w,a,b;
  scanf("%d%d%d%d\n",&h,&w,&a,&b);
  const int N=h*w;
  std::vector<std::vector<long long>> dp(1<<N,std::vector<long long> (a+1,0));
  //bitDP
  dp[0][0]=1;
  for(int bit=0;bit<1<<N;bit++){//occupy
    for(int j=0;j<a;j++){//2*1 count
      for(int i=0;i<N;i++){//start
        for(int dir=0;dir<2;dir++){//direction 0:↓ 1:→
          int newbit=bit;
          int ni=i;
          if(dir){
            if(i%w==w-1)continue;
            ni++;
          }else{
            if(i/w==h-1)continue;
            ni+=w;
          }
          if((bit>>i)&1)continue;
          newbit|=1<<i;
          if((bit>>ni)&1)continue;
          newbit|=1<<ni;

          dp[newbit][j+1]+=dp[bit][j];
        }
      }
    }
  }
  //sum&div
  long long ans=0;
  for(int bit=0;bit<1<<N;bit++){
    ans+=dp[bit][a];
  }
  for(int i=1;i<=a;i++)ans/=i;
  //output
  printf("%lld\n",ans);
  return 0;
}