問題概要
$N$匹のうさぎがいる. $M$人の観客から, うさぎ$x_i$がうさぎ$y_i$よりも先にゴールしたという情報を得た.
これら全ての情報に合致する着順が何通りあるかを求めよ.
制約
- $2\leq N\leq 16$
- $1\leq M\leq \frac{N(N - 1)}{2}$
考察
bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかを$N$bitの状態として持つ (bitが立っていればすでにゴールしているとする).
遷移
dp[n][stat]からの遷移を考える. 次に遷移する候補は, statのbitが立っていないものから選ぶ.
候補のうさぎを$p$とすると, 情報と照らし合わせたとき
- $x_i=p$なら, $y_i$はまだゴールしていないはず.
- $y_i=p$なら, $x_i$はすでにゴールしているはず.
この2つの条件を満たしていないと, 情報に合致していないと分かり, 遷移を行わない.
満たしているときは, dp[n + 1][stat + (1 << p)] += dp[n][stat]として配っていけば良い.
よって遷移に$O(M)$かかって, 全体の計算量は, $O(MN^{2}2^{N})$.
ただ, 現状この計算量だと最悪で$10^{9}$を超えてしまうので, 遷移する際に無駄な情報を見ない(うさぎ$p$に関する情報だけを集約する)ようにしてごまかした.
提出コード(C++🔆)
ll dp[22][77777];
vl after[22], before[22];
signed main() {
SS(ll, N, M);
REP(i, M) {
SS(ll, x, y);
--x, --y;
after[x].PB(y);
before[y].PB(x);
}
dp[0][0] = 1;
REP(n, N) {
REP(stat, (1LL << N)) {
// まだゴールしてないなら, dp[n][stat]からdp[n+1][stat+(1<<i)]に遷移できるか確認
REP(i, N) if ((stat & (1LL << i)) == 0) {
bool canTransit = true;
EACH(aft, after[i]) if ((stat & (1LL << aft)) != 0) canTransit = false;
EACH(bef, before[i]) if ((stat & (1LL << bef)) == 0) canTransit = false;
if (!canTransit) continue;
dp[n + 1][stat + (1LL << i)] += dp[n][stat];
}
}
}
print(dp[N][(1LL << N) - 1]);
}