DPまとめコンテスト/O - Matching - 競技プログラミング用 知識集積所【7/20更新】

---

問題

DP-O

必要知識

ABCのB以下レベルの内容は省略

• bitDP（未作成）
  • 動的計画法
  • bit全探索（未作成）
• 剰余類環

考え方

いわゆるbitDP（未作成）。
マッチングの状態をbit全探索（未作成）の要領で調べていく過程で動的計画法を用いる。

まず、DPテーブルの添字にマッチング状態をbitで表したものを取る。
例えばn=5でdp.at(13)なら、13は二進数で01101なので、男性は最初の3人（0人目1人目2人目）、女性はbitに対応する0人目2人目3人目、という3人ずつのマッチング数を意味すると決める。

そして、例えば入力例1の場合、以下のようにする。

dp.at(0)は、男性0人と女性0人のマッチング数なので、明らかに1。

dp.at(1)は、男性1人（0番）と女性1人（0番）のマッチング。
男性0番は女性0番と相性が悪いのでパス。
よってdp.at(1)は0。

dp.at(2)は、男性1人（0番）と女性1人（1番）のマッチング。
男性0番は女性1番と相性がよいので、ここをマッチングさせてみる。
これは残りは男性0人と女性0人のマッチングになるので、dp.at(0)の値である1通りとわかる。
よって、dp.at(2)は1。

dp.at(3)は、男性2人（0番、1番）と女性2人（0番、1番）のマッチング。
男性1番は女性0番と相性がよいので、ここをマッチングさせてみる。
これは残りは男性1人（0番）と女性1人（1番）のマッチングになるので、dp.at(2)の値である1通りとわかる。
男性1番は女性1番と相性が悪いのでこちらはパス。
よって、dp.at(3)は1。

dp.at(4)は、男性1人（0番）と女性1人（2番）のマッチング。
男性0番は女性2番と相性がよいので、ここをマッチングさせてみる。
これは残りは男性0人と女性0人のマッチングになるので、dp.at(0)の値である1通りとわかる。
よって、dp.at(4)は1。

dp.at(5)は、男性2人（0番、1番）と女性2人（0番、2番）のマッチング。
男性1番は女性0番と相性がよいので、ここをマッチングさせてみる。
これは残りは男性1人（0番）と女性1人（2番）のマッチングになるので、dp.at(4)の値である1通りとわかる。
男性1番は女性2番と相性がよいので、ここをマッチングさせてみる。
これは残りは男性1人（0番）と女性1人（0番）のマッチングになるので、dp.at(1)の値である0通りとわかる。
よって、dp.at(3)は1+0=1。

以下略。
最後は全男性と全女性でのマッチング数を答えればいい。

答えはmod10^9+7での値なので、剰余類環も参照。

解答例

解答例

注意点

別解