【题解】地精部落(DP)

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

转移枚举一个排列的最大值在哪里，就把序列分成了互不相干的两个部分，把其中\(i-1\choose 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\n",2ll*dp[n]%mod);

      return 0;

}