ABC196 D - Hanjo (400)
コンテスト中の考察
上の方から全状態を試す
ある行があるパターンになる場合の数を持っておいて、次の行の計算で使う
行の状態は縦横をうまく決めれば$ 2^4以下なのでできそう
半畳、一畳しか考えず畳の向きを考えてなかったので駄目
最終的な考察
$ dp[p]で立っているbitは一畳の畳が置かれている状態の時のその状態になる数を表す
$ dp[0] = 1 から始めて、縦横のどちらかに連続している2マスに畳を置いて状態遷移する
最後に全ての状態から求めたい数だけ一畳の畳が置かれている場合の数を足し合わせる
最後に$ A!で割ったのが答え
dp中の状態だとA枚を区別していないので、そのパターンで割っている?
一つの状態での計算が$ O(H^2W^2)で状態が$ 2^{HW}なので全体で$ O(2^{HW}H^2W^2)
解説のDFSがスマートに見える