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";; }