题解 AT_codefestival_2016_final_f【Road of the King】

注意到当前移动到的位置并不重要，重要的是经过的点数和 \(1\) 所在强连通分量大小，因此把它们放进状态里：设 \(f_{i,j,k}\) 表示进行 \(i\) 次移动，经过了 \(j\) 个不同的点，此时 \(1\) 所在的强连通分量大小为 \(k\) 的方案数。

考察下一次移动到的点的情况：

• 没有访问过：共有 \(n-j\) 种此类点，且此时不在 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j+1,k}\gets f_{i,j,k}\times(n-j)\)。
• 访问过，不在 \(1\) 所在强连通分量：共有 \(j-k\) 种此类点，此时依然不在 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j,k}\gets f_{i,j,k}\times(j-k)\)。
• 访问过，且在 \(1\) 所在强连通分量：共有 \(k\) 种此类点，此时所有访问过的点都并入 \(1\) 所在强连通分量，因此有转移 \(f_{i+1,j,j}\gets f_{i,j,k}\times k\)。

时间复杂度 \(O(n^2m)\)。

// Problem: Road of the King
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_codefestival_2016_final_f
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
    return x < mod ? x : x - mod;
}

template<int mod>
struct Modint {
    unsigned int x;
    Modint() = default;
    Modint(int x) : x(x) {}
    friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
    friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
    friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
    friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
    friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
    friend Modint operator^(Modint a, int k) {Modint ans = 1; for(; k; k >>= 1, a *= a) if(k & 1) ans *= a; return ans;}
    friend Modint operator~(Modint a) {return a ^ (mod - 2);}
    friend Modint operator/(Modint a, Modint b) {return a * ~b;}
    friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
    friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
    friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
    friend Modint& operator^=(Modint& a, int k) {return a = a ^ k;}
    friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
    friend Modint& operator++(Modint& a) {return a += 1;}
    friend Modint operator++(Modint& a, int) {Modint b = a; ++a; return b;}
    friend Modint& operator--(Modint& a) {return a -= 1;}
    friend Modint operator--(Modint& a, int) {Modint b = a; --a; return b;}
    friend Modint operator-(Modint a) {return a.x == 0 ? 0 : mod - a.x;}
    friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
    friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

typedef Modint<1000000007> mint;

const int N = 305;

int n, m;
mint dp[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    dp[0][1][1] = 1;
    rep(i, 0, m - 1) {
        rep(j, 1, n) {
            rep(k, 1, j) {
                dp[i + 1][j + 1][k] += dp[i][j][k] * (n - j);
                dp[i + 1][j][k] += dp[i][j][k] * (j - k);
                dp[i + 1][j][j] += dp[i][j][k] * k;
            }
        }
    }
    cout << dp[m][n][n] << endl;
    return 0;
}