Typical DP Contest M - 家

問題
提出コード

解法

bitDPです。だんだん詰め合わせ感が増えてきました。
同じ階層でからに移動するパターン数
とすると、これをの行列に見立てて乗すると、が答えになります。
を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求まります。
ということで、この行列式を完成させることを考えます。
からの部屋を通り、にいくパターン数
とします。部屋がまでしかないので、通る部屋の状態をビット列で持つことができます(自分は、スタート地点とゴール地点の両方のビットも立てました)。
このとき、は、の全ての状態に対する総和になります。
このDPは、スタート地点から幅優先探索をすることで求めることができます。
今、の部屋を通り、の部屋にいるとします。すると、に含まれていないかつ、からいくことのできる部屋については、部屋がで表されることを利用して、

という遷移を行えばよいです。
ということで、すべての部屋をスタート地点に選んだ幅優先探索を行い、このDPを埋めることで、を完成させることができます。
あとは、乗すれば、答えが求まります。