CODE FESTIVAL 2017 Elimination Tournament Round 3,F: Unicyclic Graph Counting

https://cf17-tournament-round3-open.contest.atcoder.jp/submissions/2045180

こんなのサイクルが１つあるだけのグラフ以外に考察の余地無いだろで、DPに行けたのは良かったです。

dp[i][j][k]:=i番目まで見て、j点サイクルに使って、サイクルの次数がkの時のある値として、
dp[i][j][k]*(N-j-1)!*(k-1)!/2みたいなのを足し合わせれば答えになるだろっていうところまで行きましたが、式を間違っていたためサンプル通らず…
editorialの式見て少し直してAC。

まずWA出すと方針が間違っているのではと心配になるんですよねぇ。
自信持てるようになるまで精進しないと

int N;
ll dp[2][310][610];
int d[310];

bool is_two() {
	rep(i, 0, N) if(d[i] != 2) return false;
	return true;
}

void solve() {
	cin >> N;
	C_init(2 * N);
	rep(i, 0, N) cin >> d[i];

	if(is_two()) {
		cout << fac[N - 1] * fiv[2] % mod << "\n";
		return;
	}

	dp[0][0][0] = 1;
	int now = 0, nex = 1;
	rep(i, 0, N) {
		memset(dp[nex], 0, sizeof(dp[nex]));
		rep(j, 0, N) {
			rep(k, 0, 2 * N + 1) {
				if(!dp[now][j][k]) continue;
				if(d[i] >= 2) {
					ADD(dp[nex][j + 1][k + d[i] - 2], dp[now][j][k] * fiv[d[i] - 2]);
				}
				ADD(dp[nex][j][k], dp[now][j][k] * fiv[d[i] - 1] % mod);
			}
		}

		swap(now, nex);
	}


	ll res = 0;
	rep(j, 3, N) {
		rep(k, 1, 2 * N + 1) {
			if(!dp[now][j][k]) continue;
			ADD(res, dp[now][j][k] * k % mod * fac[N - j - 1] % mod * fac[j - 1] % mod * fiv[2] % mod);
		}
	}
	cout << res << "\n";
}

てか冒頭の式なかったら結構難しいですよねこれ。有名事実なのかなぁ。