atcoder [Road of the King] 题解（DP好题）

题面

简要题意：有一个 $n$ 个点的图，目前一条边都没有。有一个人在 $1$ 号点要进行 $m$ 次移动， 终点不必是 $1$ 号点。加入第 $i$ 次的从 $u$ 移动到了 $v$， 那么 $u$ 到 $v$ 之间出现一条有向边。问一共有多少序列满足最后 $n$ 个点组成的图 是一个强联通图。答案对 $10^9+7$ 取模。 $1\le n，m\le 300$。

分析：
        注意到一个性质，就是如果要形成强联通图，那么所有的点都要和 $1$ 能够相互到达。因为是从 $1$ 出发，所以序列里所有的点 $1$ 都可以到达，只要这 $n$ 个点都能到达 $1$ ，那么这 $n$ 个点组成的图就一定是一个强联通图。 我们根据这条性质来划分状态。

        设 $d{p}_{i,j,k}$ 表示当前已经走了 $i$ 步，涉及到的点有 $j$ 个， 跟 $1$ 形成强联通的点有 $k$ 个。注意当前点可以看做是没有跟 $1$ 形成强联通的点。我们考虑转移：

        如果下一步走到了一个没有跟 $1$ 形成强联通但是已经设计的点，那么有 $(j-k)\times d{p}_{i,j,k}\to d{p}_{i+1,j,k}$。

        如果下一步走到了一个跟 $1$ 形成强联通的点，那么所有涉及到的点都会和 $1$ 形成强联通，有 $k\times d{p}_{i,j,k}\to d{p}_{i+1,j,j}$。

        如果下一步走到了一个还未涉及到的点，那么有 $(n-j)\times d{p}_{i,j,k}\to d{p}_{i+1,j+1,k}$。

        最后输出 $d{p}_{m,n,n}$ 就好了。

#include<bits/stdc++.h>
#define N 310
#define LL long long
#define mod 1000000007
using namespace std;
int n, m;
LL dp[N][N][N];// dp[i][j][k] 表示走了i步，已经拓展了j个点， 能与1形成强联通的点数为k 的方案数 
int main(){cin >> n >> m;dp[0][1][1] = 1LL;for(int i = 0; i <= m; i++){for(int j = 1; j <= n; j++){for(int k = 1; k <= j; k++){dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k] * (1LL * (n - j))) % mod;dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k] * (1LL * (j - k))) % mod;dp[i + 1][j][j] = (dp[i + 1][j][j] + dp[i][j][k] * (1LL * k)) % mod;}}}cout << dp[m][n][n] << endl;return 0;
}