题意简化
给定一个数 \(n\)，求满足以下二者条件之一的 \(n\) 的排列的个数：1、对于所有奇数项，大于所有与它相邻的项；2、对于所有奇数项，小于所有与它相邻的项，由于答案可能很大，输出答案对 \(mod\) 取模后的值。
做法
易得到两种情况的个数是相等的（可以自己打小数据的表），所以我的思路是在加入一个新的大数后，奇数项较大的情况有多少。
所以这个大数应该是放在奇数项，然后对于放在 \(j\) 位置，左边的就应有 \(f[j-1]\) 种情况，右边则为 \(i-j\) 。
我们还想到左边这 \(j-1\) 个数肯定不是固定的，所以我们还需要组合数，来求出这 \(j-1\) 可能的组合情况。
那么组合数如何求呢？我们想到了一个有趣的模型——杨辉三角。为了节省空间，我们可以在递推 \(dp\) 时，采用倒着的顺序顺带着将组合数求出，这样可以避免错误，组合数也只需要一维数组即可。
所以此题的两个核心式子便得到了。最后将得到的 \(dp\) 乘2，对于 \(n\) 为1特判即可。
代码
#include<bits/stdc++.h>
using namespace std;
unsigned long long f[2005],ms,n,c[2005],cs=2;
int main()
{
//freopen("dp.in","r",stdin);
//freopen("dp.out","w",stdout);
cin>>n>>ms;
f[1]=1;
f[0]=1;
c[1]=1;//初始化，这里将杨辉三角右移了一下
for(int i=2;i<=n;i++){
for(int j=i;j>=1;j--){
//cout<<j<<" "<<c[j-1]<<endl;
c[j]+=c[j-1];//杨辉三角递推式
c[j]%=ms;
if(j&1)f[i]=(f[j-1]*f[i-j]%ms*c[j]+f[i])%ms;//dp转移式
}
}
if(n==1){//特判
cout<<1<<endl;
return 0;
}
cout<<(f[n]*cs)%ms<<endl;
return 0;
}