[文章目录]
Description
求1~n的全排列的方案数%p的值，满足对于每个ai都有ai>ai-1&&ai>ai+1或者ai< ai-1&& ai< ai+1（波浪形）。3≤N≤4200 p<=10^9
DP
f[i]表示1~i的合法全排列，并且a1>a2的方案数。g[i]表示1~i的合法全排列，并且a1< a2的方案数。枚举1的位置，能够知道两边区间的答案，乘法原理+组合数（滚动数组）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,p,C1[5000],C2[5000],f[5000],g[5000];
int main()
{
scanf("%lld%lld",&n,&p);
C1[0]=1;
f[1]=g[1]=f[0]=g[0]=1;
for(int i=2;i<=n;++i)
{
swap(C1,C2); C1[0]=1;
for(int j=1;j<=i-1;++j) C1[j]=(C2[j]+C2[j-1])%p;
for(int j=1;j<=i;++j)
{
if(j&1) g[i]=(g[i]+g[j-1]*f[i-j]%p*C1[j-1]%p)%p;
else f[i]=(f[i]+f[j-1]*f[i-j]%p*C1[j-1]%p)%p;
}
}
printf("%lld",(f[n]+g[n])%p);
return 0;
}