CODEFESTIVAL 2016 Final F-Road of the King(1000)

問題

atcoder.jp
高橋くんが、まだ辺が存在しない $N$ 頂点のグラフに、 $M$ 回任意の頂点へ移動しながら有向辺を張っていく。はじめは頂点 $1$ にいる。
$M$ 回の移動後にそのグラフが強連結になっているような移動の仕方の通りの数を求める問題。

制約

$1 \leq N, M \leq 300$

解法

基本的な考察

この問題には次の重要な考察がある。

頂点 $1$ 以外に頂点の区別が存在しない $(1)$
頂点 $1$ へ移動した時に、向かったことのある頂点全てが強連結グラフになる。
その後も頂点 $1$ を含む強連結グラフの頂点へ移動する事で、向かったことのある頂点全てが強連結グラフになる。 $(2)$

$(2)$ について解説する。
頂点 $1$ へ再び向かえるようにするには、高橋くんがもう一度頂点 $1$ を通るしか無いのは明らかだろう。そのため、頂点 $1$ を通ってみる。すると閉路が完成するため、今まで通ってきた頂点は全て強連結グラフになる。
また、頂点 $1$ を含む強連結グラフができたら、次は必ずしも頂点 $1$ につなぐ必要はなく、頂点 $1$ を含む強連結グラフに繋げば、頂点 $1$ を通れるため、これも同様に今まで通ってきた頂点が全て強連結グラフになる。

解く

この問題を全探索を用いて解くことを考える。

とりあえず、強連結グラフになる/ならないを考慮しない時を考えてみる。
まず、今までに何回移動したかを保存する $i$ は状態として必要である。
次に、 $(1)$ を利用すると、巡回した頂点の数 $j$ がわかっていれば、頂点の数を $j+1$ に増やす場合の数は $N - j$ 通り存在することが分かり、増やさない時は $j$ 通りあるということがわかるのでこれで $M$ 回動かして $N$ 頂点を辿る場合の数は求められる。

次に、グラフが強連結グラフにならないといけないことを考慮してみる。
基本的な方針は同じで $i$ 回移動した時に $j$ 頂点たどっているという情報は変わらず必要である。
$(2)$ を利用すると、 $k$ 頂点が頂点 $1$ を含む強連結グラフに含まれているという情報だけ加えれば解くことが出来る事がわかる。
$k$ があると、強連結グラフの頂点に移動する場合の数が$k$ 通りであると表現できるからである。
強連結グラフに含まれないすでに行ったことのある頂点に行く場合の数は $j - k$ 通り、新しい頂点に行く時は $N - j$ 通りあることがわかる。
うまく遷移させて上げると見落としなく計算が出来る。

実は $i, j, k$ の状態が決まっていればこの先の遷移は全て同じになる。
そのため、状態をまとめることが出来、 $DP[i][j][k]$ を用いて計算量 $O(MN^2)$ で計算することが出来る。

ソースコード

long long dp[305][305][305] = {};
int main() {
    int N, M;
    cin >> N >> M;
 
    dp[0][1][1] = 1;
    for (int i = 0; i < M; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (dp[i][j][k] == 0) continue;
                (dp[i + 1][j + 1][k] += (N - j) * dp[i][j][k]) %= mod;
                (dp[i + 1][j][j] += k * dp[i][j][k]) %= mod;
                (dp[i + 1][j][k] += (j - k) * dp[i][j][k]) %= mod;
            }
        }
    }
 
    cout << dp[M][N][N] << endl;
 
    return (0);
}