CODE FESTIVAL 2016 Final,F: Road of the King

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

これは簡単だった。

どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。
なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含む連結成分の大きさがkとした時の場合の数)とすればできます。

int N, M;
ll dp[2][310][310];

void solve() {
	cin >> N >> M;
	dp[0][N - 1][1] = 1;
	
	int now = 0, nex = 1;
	rep(i, 0, M) {
		memset(dp[nex], 0, sizeof(dp[nex]));
		rep(j, 0, N + 1) {
			rep(k, 0, N + 1) {
				if(!dp[now][j][k]) continue;
				if(j != 0) ADD(dp[nex][j - 1][k], dp[now][j][k] * j % mod);
				if(N - j - k > 0) ADD(dp[nex][j][k], dp[now][j][k] * (N - j - k) % mod);
				ADD(dp[nex][j][N - j], dp[now][j][k] * k % mod);
			}
		}
		swap(now, nex);
	}
	cout << dp[now][0][N] << "\n";;
}