Matching [Educational DP Contest / DP まとめコンテスト O]

https://atcoder.jp/contests/dp/tasks/dp_o

前提知識

• bitDP

解説

https://atcoder.jp/contests/dp/submissions/3973687

bitDPで解くのだろうという推測は制約からできる。
無計画に数えると、同じパターンを数え上げてしまうので、男性の方は1,2,,...と固定にして、女性をN!通り考えることで、重複なく数え上げることにする。
すると、男性は何番目まで、女性は誰が残っているかが肝になるので、これでbitDPを作る。
dp[i][msk] := i番目の男性までマッチングが終わっていて、mskの女性のマッチングが終わっているときの組み合わせ
各状態からの遷移はi+1番目の男性とj番目の女性のマッチングを全て試すことになる。
よって、全状態O(N2^N), 遷移O(N)なので、O(N^2*2^N)となる。
これはギリギリ間に合わない。
　
ここから状態をへらすことを考えるが、mskで1が立っている数を数えるとiと等しくなっていることが分かる。
これは、ペアが決まっている男性の数と女性の数が一致するためである。
なので、有効な状態は実際はO(2^N)しかない。
なので、有効な状態のときのみ遷移を行うことにする。
すると、無効な状態ではO(N*2^N), 有効な状態ではO(2^N*N)となり、全体としては計算量O(N2^N)となり間に合う。

int N, A[21][21];
mint dp[22][1 << 21];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];
 
    dp[0][0] = 1;
    rep(i, 0, N) rep(msk, 0, 1 << N) if(i == __builtin_popcount(msk)) {
        rep(j, 0, N) if (!(msk & (1 << j))) if (A[i][j]) {
            dp[i+1][msk | (1 << j)] += dp[i][msk];
        }
    }
 
    cout << dp[N][(1 << N) - 1] << endl;
}