\(F(a, b, s) =\) 畳を\(a\)枚使用、半畳を\(b\)枚使用し、部屋の中で既に敷かれている床の集合が\(s\) である場合の数

という関数を考えます。

また、\(s\) の要素を数値で表すとき、上に行くほど小さく、行が同じならば左ほど小さいとします。

例

|0|1|2|
|3|4|5|
|6|7|8|

初期状態から

\[ \begin{aligned} F(a, b, 1 << (H*W) - 1) &=& 1( a = Aかつb = Bのとき)\\ &=& 0( a \neq Aまたはb \neq Bのとき) \end{aligned} \]

です。

ここで、\(s\)のうちまだ敷かれていない最小のインデックスを\(t\)とします。\(t\) は \(s\)をビット反転した値の最下位ビット(LSB)から求められます。

すると、

\[ \begin{aligned} F(a, b, s) &=& (半畳をt に置く場合の数)\\ &+& (畳をt とその右に置く場合の数)\\ &+& (畳をt とその下に置く場合の数) \end{aligned} \]

という遷移が考えられます。

畳を重ねて置いてしまう場合も判定してしまっていますが、そのような場合は最終的に\(F(a \neq A, b \neq B, 1 << (H*W) - 1) = 0\)にたどり着くため必ず \(0\) となり影響ありません

これは、境界値判定を省略すると

\[ \begin{aligned} F(a, b, s) &=& F(a, b-1, s \mathbin{|} 1 << t)\\ &+& F(a, b-1, s \mathbin{|} 1 << t \mathbin{|} 1 << (t+1))\\ &+& F(a, b-1, s \mathbin{|} 1 << t \mathbin{|} 1 << (t+H))\\ \end{aligned} \]

と再帰関数で表せます。

よって、答え \(F(A, B, 0)\) が求められます。

この問題の場合は \(F\) の戻り値をメモ化しなくても問題ありませんが、このような再帰による動的計画法ではメモ化するようにしておいたほうが無難です。

解答例 C#