【题解】地精部落(DP)

【题解】地精部落(DP)

设(f_i)表示强制第一个是谷的合法方案数

转移枚举一个排列的最大值在哪里，就把序列分成了互不相干的两个部分，把其中(i-1choose j-1)的数字分配给前面部分，剩下的给后面。转移从所有可以转移的偶数过来

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>


using namespace std;  typedef long long ll;
inline int qr(){
      register int ret=0,f=0;
      register char c=getchar();
      while(c<48||c>57)f|=c==45,c=getchar();
      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
      return f?-ret:ret;
}
const int maxn=5005;
int c[maxn][maxn];
int dp[maxn];
int mod,n;

int main(){
      dp[0]=dp[1]=c[0][0]=1;
      n=qr();mod=qr();
      for(register int t=1;t<=5000;++t){c[t][0]=1;
	    for(register int i=1;i<=t;++i)
		  c[t][i]=(c[t-1][i-1]+c[t-1][i])%mod;}
      for(register int t=2;t<=n;++t)
	    for(register int i=2;i<=t;i+=2)
		  dp[t]=(dp[t]+1ll*c[t-1][i-1]*dp[i-1]%mod*dp[t-i]%mod)%mod;
      printf("%lld
",2ll*dp[n]%mod);
      return 0;
}