白駿1670首脳会談2

質問リンク

https://www.acmicpc.net/problem/1670

質問する

に答える

ある人を基準に、一人一人と握手する場合を分けて考えてみましょう.
1.時計回りに距離のある人と握手
直線を基準に2つの領域に分けられ、1つの領域は0人、もう1つの領域は6人です.
ケース数:dp[0]x dp[6]

2.時計回りに2コマ離れた人と握手
同様に、2つの領域に分けられ、各領域の人は奇数であり、誰もが握手できる場合はない.
ケース数:0

3.時計回り3コマの人と握手
ケース数:dp[2]x dp[4]

4.時計回りの四角い人と握手
ケース数:0

5.時計回り5コマの人と握手
ケース数:dp[4]x dp[2]

6.時計回り6コマの人と握手するとき
ケース数:0

7.時計回り7コマの人と握手
ケース数:dp[6]x dp[0]

dp[8] = (dp[0] x dp[6]) + (dp[2] x dp[4]) + (dp[4] x dp[2]) + (dp[6] x dp[0])
dp[n] = (dp[0] x dp[n-2]) + (dp[2] x dp[n-4]) + ... +(dp[n-2] x dp[0] )

コード#コード#

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define MOD 987654321
typedef long long ll;
ll dp[10001];
int main(void) {
	int n;
	cin >> n;
	dp[2] = dp[0] = 1;
	for (int i = 4; i <= n; i += 2) {
		for (int j = 2; i - j >= 0; j += 2) {
			dp[i] = (dp[i] + (dp[j-2] * dp[i - j]) % MOD) % MOD;
		}
	}
	cout << dp[n];
}

ポスト

普段はdp問題に弱いのでびっくりしましたが、この問題はまあまあです.ゴールド2ですが、前回解決した色の償還問題はもっと難しいと思います.