問題概要
$N$人の男と$N$人の女同士で$N$組のペアを作る通り数を$10^9 + 7$で割った余りを求めなさい.
但し, それぞれの男女には相性があり, $a_{i,j}$は男$i$と女$j$の相性を表すものとする.
制約
- $1 \leq N \leq 21$
考察
制約がbitDPだと言っているので従う.
とりあえず安直に考えると, 「$dp[i][msk] := i$人目の女と組み合わせる通り数 (男は$msk$だけ残っている)」となる.
だけどこれだと状態数が$O(N2^N)$, 遷移が$O(N)$なので全体で$O(N^22^N)$になってしまう (さすがに厳しい).
ここで, $msk$さえ分かれば$i$が求まることに着目すると状態数を$O(2^N)$に落とせる.
よって, 全体で$O(N2^N)$でこの問題は解けた.
提出コード(C++🔆)
signed main() {
SS(int, N);
SVV(int, A, N, N);
vector<int> bits(N, 0);
REP(i, N) REP(j, N) bits[i] |= A[j][i] << j;
vector<pair<int, int>> topo;
REP(i, 1 << N) topo.emplace_back(__builtin_popcount(i), i);
RSORT(topo);
auto dp = make_v<modint>(1 << N);
dp[(1 << N) - 1] = 1;
REP(i, 1 << N) {
int cnt, bit;
tie(cnt, bit) = topo[i];
int cand = bit & bits[N - cnt];
REP(j, N) if ((1 << j) & cand) {
int nxt = bit ^ (1 << j);
dp[nxt] += dp[bit];
}
}
print(dp[0]);
}