OMC130-B修正前ver

修正前の問題文:「a,b,c,dが相異なる」の場合

以下の条件を満たす通り数dp[n]を考える
１：n人存在する
２：n人全てが、いずれかの人と赤or青の糸で結ばれている
３：問題の２条件と最終的な状態の条件を満たす。

以上を満たすdp[n]が求まれば、元の問題の答えは
ans=ΣBinom(15,i)*dp[i]になるのは明らか。

dp[n]を具体的に考えていく。
a < b < cに対して
人aと人cが間接的(直接も含む)に結ばれている場合
人bも人a、人cと間接的(直接も含む)に結ばれているのは明らか
(最終的な状態を満たさなくなるため)

つまりn人は間接的に結ばれている人の集合で分割されることがわかる。

以下の条件を満たす通り数subdp[n]を考える
１：n人存在する
２：n人全てが、間接的(直接も含む)に結ばれている
３：問題文の２条件と最終的な状態の条件を満たす。

これを求めることができれば、dp[i] = Σsubdp[i-j]dp[j]でdpが求まる。

subdp[n]について考える
n= 1の時subdp[n] = 0は明らか
n= 2の時subdp[n] = 2は明らか
n= 3の時
1-2-3
1-3-2
2-1-3の結び方が条件を満たすためsubdp[n] = 6
n>3の時
1-2-3........(n-1)-n
2-1-3-......(n-1)-n
1-2-3........-n-(n-1)
2-1-3........-n-(n-1)の結び方が条件を満たすためsubdp[n] = 8
となる。
よってdp[n]が求まり元問題の答えも求まった。
※subdp[n] = 2 (n>=2)とすると修正後の問題の答えとなる

void omc130b(int n) {//本問は n= 15
	vector<long long>dp(n + 1);
	dp[0] = 1;
	rep2(i, 1, n + 1) {
		if (i >= 2)dp[i] += dp[i - 2] * 2;
		if (i >= 3)dp[i] += dp[i - 3] * 6;
		rep(j, i - 3)dp[i] += dp[j] * 8;
	}
	long long ans = 0;
	rep(i, n + 1)ans += Binom[n][i] * dp[i];
	cout << ans << endl;
}