更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19349977

思路

由于题目的数据范围，我们可以得知，大概是个 $n ^ 3$ 的玩意。

但是我们需要仔细想想怎么计数？

首先，这个玩意和什么有关?

第一肯定是步数，第二是点是否走过，第三是这个点和为我们要的强连通图的关系。

然后我们考虑最难的问题，就是这个强连通图怎么判断，怎么累加答案？我们走到一个点的时候怎么判断其是否能与原来的形成一个强连通呢？还是说其目前自己和其他点成强连通，需要后续的操作去整。

不难发现，其实一个点，其强连通关系只有两种，第一种就是和起点在一个强连通里面，第二种，就是不在起点的强连通里面。

我们定义 $f_{i, j, k}$ 表示目前已经走了 $i$ 步，已经访问了 $j$ 个点，与起点 $1$ 形成的强连通的大小为 $k$。（以下所说的形成强连通均是与 $1$ 形成）

考虑转移。

首先走到点，第一种情况，是没有走过，于是我们有：

$f_{i + 1, j + 1, k} \to f_{i + 1,j + 1, k} + f_{i, j, k} \times (n - j)$

第二种，是走过，但是没有形成强连通的点：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times (j - k)$

第三种是，走过，且已经形成了强连通：

$f_{i + 1, j, k} \to f_{i + 1, j, k} + f_{i, j, k} \times k$

于是我们的答案就在 $f_{m, n, n}$。

代码

#include<iostream>
using namespace std;

#define int long long

const int MAXN = 305;
const int MOD = 1e9 + 7;

//f[i][j][k] 走了 i 步，访问了 j 个点，以 1 为根的 scc 大小为 k
int f[MAXN][MAXN][MAXN];

int n, m;

signed main(){
	freopen("rotk.in", "r", stdin);
	freopen("rotk.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	f[0][1][1] = 1;
	
	for(int i = 0;i <= m - 1;i ++){
		for(int j = 1;j <= n;j ++){
			for(int k = 1;k <= n;k ++){
				if(!f[i][j][k]) continue;
				//没走的
				f[i + 1][j + 1][k] += f[i][j][k] * (n - j) % MOD;
				f[i + 1][j + 1][k] %= MOD;
				//走过，但不在 1 的scc
				f[i + 1][j][k] += f[i][j][k] * (j - k) % MOD;
				f[i + 1][j][k] %= MOD;
				//走过，在 1 的 scc
				f[i + 1][j][j] += f[i][j][k] * k % MOD;
				f[i + 1][j][j] %= MOD;
			}
		}
	}
	
	cout << f[m][n][n] % MOD << '\n';
	return 0;
}

$\mathrm {Subtask}1: n\le 5$。

直接 $\mathcal O(n^m)$ 爆搜，暴力判强连通即可。

$\mathrm{Subtask} 2: n\le 15$。

这个我没有写，不知道对不对。

考虑状压 dp。

思考强连通图的形成过程，一定是从 $1$ 所在的强连通分量中的某个点出发，走到某些还不在这个强连通分量的点，然后走回 $1$ 所在的强连通分量中的某个点。

并且，我们并不关心起点终点具体是那个点。

据此，设 $f(S,t)$ 表示 $t$ 秒后 $1$ 所在的强连通分量为 $S$ 的方案数。

转移大概就是设 $g(S,t)$ 表示经过 $t$ 秒经过了 $S$ 中这些点的方案数，然后转移做一个二维的合并：$f(S_1,t_1)\times g(S_2,t_2)\to f(S_1\cup S_2, t_1+t_2)[S_1\cap S_2 = \emptyset]$。

复杂度 $\mathcal O(3^n \mathrm{poly}(n))$。

$\mathrm{Subtask 3}:n\le 300$。

考虑优化状压 dp。两种方法优化到正解：重构 dp 状态，分步转移。两者殊途同归。

因为我们并不关心 $1$ 所在的强连通分量具体是啥，所以设 $f(i,j,k)$ 表示 $i$ 次操作后 $1$ 所在的强连通分量大小为 $j$，目前往外扩展了 $k$ 个新点的方案数。

初始状态 $f(0,1,0)=1$。三种转移，分别对应走回 $1$ 所在的强连通分量，走一个新点，走到一个还在构建的点。

$$f(i,j,k)\times j\to f(i+1,j+k,0)$$

$$f(i,j,k)\times (n-j-k)\to f(i+1,j,k+1)$$

$$f(i,j,k)\times k\to f(i+1,j,k)$$

答案就是 $f(m,n,0)$。

注意！！！这里有个大坑点！！！

模数是 $10^9 + 7$ 而不是 $998244353$。有人缺省源里 $\mathrm{mod}=998244353$ 调了一年。