EDPC O - Matching

マッチング

考え方

ABCでいうと、E問題級。

いわゆる bitDP。
マッチングの状態を bit で表したものを添字に取り、その状態ごとのマッチング数を動的計画法で求める。

dp[i] を、女性の集合を bit で表したものが i であるときのマッチング数とする。
ただし、男性側は「最初の popcount(i) 人」を見ていることにする。

たとえば、$n=5$ で i=13 なら、$13$ は二進数で 01101 である。
このとき、男性は最初の $3$ 人、つまり $0,1,2$ 人目で、女性は bit に対応する $0,2,3$ 人目である。
dp[13] は、この $3$ 人ずつのマッチング数を意味する。

状態 i を考えるとき、最後に追加された男性は popcount(i)-1 人目である。
この男性を、集合 i に含まれる女性 j とペアにすると、残りは i^(1<<j) の状態になる。

したがって、dp[i] は、i 内の相性がよい全ての女性 j について、dp[i^(1<<j)] の値を足せばよい。

計算量は $O(N2^N)$。

入力を受け取る。

n: 3
a:
  {0, 1, 1}
  {1, 0, 1}
  {1, 1, 1}

女性 $0,1,2$ に対応する bit を下位から並べ、使っている女性を $1$ とする。

立っている bit の数だけ、男性を $0$ 番から順に使っている状態と考える。

誰も使っていない 000 のマッチングは $1$ 通りである。

001 では、男性 $0$ 番と女性 $0$ 番を組ませる。
この $2$ 人は相性が悪いので、$0$ 通りである。

010 では、男性 $0$ 番と女性 $1$ 番を組ませる。
この $2$ 人は相性がよいので、$1$ 通りである。

011 では、男性 $0,1$ 番と女性 $0,1$ 番を組ませる。

男性 $1$ 番は女性 $0$ 番とは組める。
女性 $1$ 番とは組めない。

そのため、男性 $1$ 番と女性 $0$ 番を組ませる。
残る男性 $0$ 番と女性 $1$ 番も相性がよい。
したがって、011 は $1$ 通りである。

全ての状態について求めると、次のようになる。

111 は全員を使う状態である。

男性 $2$ 番は、全ての女性と相性がよい。
女性 $0$ 番と組む場合、残りの組み方は 110 の $1$ 通りである。
女性 $1$ 番と組む場合は、101 の $1$ 通りである。
女性 $2$ 番と組む場合は、011 の $1$ 通りである。

したがって、全員を組ませる方法は $1+1+1=3$ 通りである。
答えは $3$。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算をするたびに結果を % 1000000007 する。

特になし。