题解：UVA12887 The Soldier's Dilemma

封面

引用站外地址，不保证站点的可用性和安全性
洛谷文章链接
xyx404

思路：

设第一个士兵与第 2k+12k+1 个士兵配对（k≥0k \ge 0），则：

  • 左侧：前2k个士兵必须形成合法分组，方式数为 CkC_k。
  • 右侧：剩余 2(n−k−1)2(n-k-1) 个士兵形成合法分组,方式数为 Cn−k−1C_{n-k-1}。

综上：

Cn=∑k=0n−1Ck×Cn−k−1C_n=\sum_{k=0}^{n-1} C_k \times C_{n-k-1}

可以发现其实就是卡塔兰数。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL T,n;
LL C[5100];
const int Mod=1e9+7;
int main(){
	C[0]=1;
	for(int i=1;i<=5005;i++){
		for(int k=0;k<i;k++){
			C[i]+=C[k]*C[i-k-1]%Mod;
			C[i]%=Mod;
		}
	}
	cin>>T;
	while(T--){
		cin>>n;
		cout<<C[n]<<"\n";
	}
	return 0;
}