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}

dp[i] を、女性集合 i と、男性の最初 popcount(i) 人とのマッチング数とする。

まず、男性 $0$ 人と女性 $0$ 人のマッチング数は $1$ 通りである。

dp[0] = 1

dp[1] は、男性 $0$ 番と女性 $0$ 番のマッチングである。
しかし、男性 $0$ 番と女性 $0$ 番は相性が悪いので、dp[1] = 0 である。

dp[1] = 0

dp[2] は、男性 $0$ 番と女性 $1$ 番のマッチングである。
男性 $0$ 番と女性 $1$ 番は相性がよいので、女性 $1$ 番を取り除いた dp[0] の値を足す。

dp[2] = dp[0]
      = 1

dp[3] は、男性 $0$ 番、$1$ 番と、女性 $0$ 番、$1$ 番のマッチングである。
最後に男性 $1$ 番を追加したと考える。

男性 $1$ 番と女性 $0$ 番は相性がよいので、女性 $0$ 番を取り除いた dp[2] の値を足す。
男性 $1$ 番と女性 $1$ 番は相性が悪いので、こちらは足さない。

dp[3] = dp[2]
      = 1

dp[4] は、男性 $0$ 番と女性 $2$ 番のマッチングである。
男性 $0$ 番と女性 $2$ 番は相性がよいので、dp[0] の値を足す。

dp[4] = dp[0]
      = 1

dp[5] は、男性 $0$ 番、$1$ 番と、女性 $0$ 番、$2$ 番のマッチングである。
最後に男性 $1$ 番を追加したと考える。

男性 $1$ 番と女性 $0$ 番は相性がよいので、女性 $0$ 番を取り除いた dp[4] の値を足す。
男性 $1$ 番と女性 $2$ 番も相性がよいので、女性 $2$ 番を取り除いた dp[1] の値を足す。

dp[5] = dp[4] + dp[1]
      = 1 + 0
      = 1

同じようにして、dp[6] は次のようになる。

dp[6] = dp[2]
      = 1

最後に、dp[7] を考える。
これは全ての女性を使う状態で、最後に男性 $2$ 番を追加したと考える。
男性 $2$ 番は全ての女性と相性がよいので、女性 $0$ 番、$1$ 番、$2$ 番をそれぞれ最後に対応させる場合を足す。

dp[7] = dp[6] + dp[5] + dp[3]
      = 1 + 1 + 1
      = 3

dp[7] の $3$ が答え。

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

特になし。