组合数学+DP
传送门：GO
参见dalao的题解：GO
设f[i]表示长度为i的山脉有几种。
f[i]=f[j]*f[i-1-j]*C(i-1,j)
意思是在1~i-1枚举一个最大值j，分别取j个和i-j-1个划为两部分，两部分乘上就是当前i的答案，注意还要乘以方案数的组合数。
剩下的用杨辉三角组合数递推+滚动数组优化即可。
注意数据范围。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long li; 4 li read(){ 5 li x=0,f=1; 6 char c=getchar(); 7 while(!isdigit(c)){ 8 if(c=='-') f=-1; 9 c=getchar(); 10 } 11 while(isdigit(c)){ 12 x=x*10+c-'0'; 13 c=getchar(); 14 } 15 return x*f; 16 } 17 const int N=5000; 18 li n,p; 19 li f[N]; 20 li c[3][N]; 21 int main(){ 22 n=read();p=read(); 23 f[0]=f[1]=1; 24 c[0][0]=c[1][0]=c[1][1]=1; 25 for(int i=2;i<=n;i++){ 26 for(int j=1;j<=i;j++){ 27 c[i&1][j]=(c[(i&1)^1][j-1]+c[(i&1)^1][j])%p; 28 } 29 for(int j=0;j<i;j++){ 30 if(j&1){ 31 (f[i]=(f[i]+((c[(i&1)^1][j]*f[j])%p)*f[i-1-j])%p)%=p; 32 } 33 } 34 } 35 printf("%lld",(f[n]*2)%p); 36 return 0; 37 }