いやこれ誤読なければ解けてるな。
https://community.topcoder.com/stat?c=problem_statement&pm=15896&rd=17805
問題
面積300以下のグリッドが与えられる。
一部のマスはすでに埋まっている。
空いているマスを1*KまたはK*1の形状の矩形で埋めるとき、その埋め方は何通りか。
解法
縦か横のどちらかは17以下になるので、必要なら回転して横幅を17以下とする。
上の行からBitDPで埋めていこう。
f(r,mask) := r行目において、(r+1)行目から上向きに連結したい列をbitmaskで指定されたとき、その通り連結できる組み合わせ
とする。
g(r,mask) := r行目において、(r+1)行目から上向きに連結可能な列がちょうどbitmaskの通りである組み合わせ
とする。
g(0,0)=1から初めて、g(r,*)からf(r,*)を求め、g(r+1,*)を求める、ということを順次行っていこう。
前者はg(r,*)を高速ゼータ変換で足しこむことでf(r,*)を求められる。
あとはf(r,*)からg(r+1,*)を求めるパートである。
まず、(r+1)列目で左に連結するマスをbitmaskで総当たりしよう。
左がすでに埋まったマスだったり、グリッド外である場合、そのbitmaskは無効である。
そうすると左右方向に連結する列が定まるので、残りのマスは上に連結してもいいししなくてもよい。
よってそのような上方向に連結可否が選べるbitmaskをbmとすると、bmの部分集合をsubmaskとすればf(r,submask)の合計が元の横方向連結を定めたときに組み合わせとなる。
なので、1行あたり高速ゼータ変換パートでO(2^W logW)、bitmask総当たりと部分集合を選ぶパートでO(3^W)で行ける。
ll from[1<<17]; ll to[1<<17]; const ll mo=1000000007; int A[303]; class DominoPlacement { public: int countWays(vector <string> T) { int H=T.size(); int W=T[0].size(); ZERO(A); int y,x,mask; if(W>H) { FOR(y,H) FOR(x,W) if(T[y][x]=='#') A[x] |= 1<<y; swap(H,W); } else { FOR(y,H) FOR(x,W) if(T[y][x]=='#') A[y] |= 1<<x; } ZERO(from); from[0]=1; FOR(y,H) { ZERO(to); FOR(mask,1<<W) { if(mask&1) continue; int cmask=mask|(mask>>1); if(A[y]&cmask) continue; //cout<<y<<" "<<mask<<endl; int cand=((1<<W)-1)^(A[y]|cmask); for(int sub=cand;sub>=0;sub--) { sub&=cand; (to[cand]+=from[sub])%=mo; } to[cand]%=mo; } swap(from,to); FOR(x,W) FOR(mask,1<<W) if((mask&(1<<x))==0) (from[mask]+=from[mask^(1<<x)])%=mo; } return from[0]; } }
まとめ
本番1辺300と勘違いした…。