B. 「NOIP2021模拟赛 By ZJ B」地精部落 题解

题目链接

B. 「NOIP2021模拟赛 By ZJ B」地精部落

solve

对于一个波动的序列，我们可以先强制将它定位第一个是山谷，（最后答案乘二就好了）

我们可以定义 \(F[i]\) 表示长度为 \(i\) 的，第一个为山谷的序列的方案数

我们枚举 \(i\) 对于每个 \(i\) 都是当前的最大值，所以必定做一个山峰，那么显然枚举 \(i\) 在 \(j\) 这个位置，分成两段，\(j-1\) 必然是奇数，不然不能保证第一个是山谷的性质，我们调出 \(j-1\) 个放在前面，由于我们只对数的相对大小感兴趣，所以组合就好了

\[F[i]=F[j-1]\times F[i-j]\times C_{i-1}^{j-1} \]

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=4205;
int N,TT,F[maxn],C[maxn][maxn];
void make_C(){
	for(int i=0;i<=N;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%TT;
	}
}
int main(){
	cin>>N>>TT;
	make_C();
	F[1]=1;F[0]=1;
	for(int i=2;i<=N;i++){
		for(int j=1;j<i;j+=2)
		F[i]=(F[i]+1ll*F[j]*F[i-j-1]%TT*C[i-1][j]%TT)%TT;
	}
	printf("%d\n",(F[N]<<1)%TT);
	return 0;
}