CODE FESTIVAL 2016 Final: F - Road of the King

,

http://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_f

$1000$点のわりに苦労なく解けた。 本番で触らなかったのが悔やまれる。

solution

DP。$O(N^2M)$。

単純に考えると、各頂点を始めて訪れる時刻に注目したい。 $1$は最後に訪れなければならないとして、その他の頂点をいくつ訪れたかでDP (時刻と訪問数から数、$\mathrm{dp}: (M+1) \times (N+1) \to \mathbb{N}$)にする、というのが思い浮かぶかもしれない。 しかし$1$を最後に訪れるというのには嘘で、$N = 5$のとき$1 \to 2 \to 3 \to 1 \to 2 \to 4 \to 5 \to 2$のような遷移が反例。

このような反例は$1$を含む強連結成分によるもの。 そこで$1$を含む強連結成分の大きさを状態に加えて、$\mathrm{dp}: (M+1) \times (N+1) \times (N+1) \to \mathbb{N}$という関数にすれば答えがでる。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
const int mod = 1e9+7;
int main() {
    int n, m; cin >> n >> m;
    auto dp = vectors(m+1, n+1, n+1, ll());
    dp[0][1][0] = 1;
    repeat (i,m) {
        repeat (j,n+1) {
            repeat (k,n+1) if (j+k <= n) {
                dp[i][j][k] %= mod;
                dp[i+1][j+k][0] += dp[i][j][k] * j % mod;
                dp[i+1][j][k]   += dp[i][j][k] * k % mod;
  if (k+1 <= n) dp[i+1][j][k+1] += dp[i][j][k] * (n-j-k) % mod;
            }
        }
    }
    cout << dp[m][n][0] % mod << endl;
    return 0;
}