↓ 跳过正文
题解：UVA12887 The Soldier's Dilemma

题解：UVA12887 The Soldier's Dilemma

xyx404
作者
xyx404
Have a nice day.
目录

封面

{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/87ccj4j3 %}

思路：
#

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

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

综上：

$$C_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;
}