对于 20%的数据，满足 N≤10；
对于 40%的数据，满足 N≤18；
对于 70%的数据，满足 N≤550；
对于 100%的数据，满足 3≤N≤4200，P≤109
首先可以发现这个序列的特点就是折来折去的，这玩意儿叫波动数列，它有一个性质叫对称性。
假如$n=5$的一个波动数列为$5,2,4,1,3$，那么他对称的序列就是$1,4,2,5,3$，可以发现原序列的对称数列也是一个波动数列。
那么我们设$f[i][j]$表示前$i$个数构成的排列第一个数的取值范围为$[1,j]$且第一个数为山峰的方案数。
首先很显然，若第一个数为$[1,j-1]$则$f[i][j]+=f[i][j-1]$。
若第一个数为$j$，剩下$i-1$个数离散一下就是一个大小为$i-1$的数集，且这个数集开头必须选$[1,j-1]$，但是$f$数组记录的是第一个数为山峰的值，这个时候就可以根据上面提到的对称性转化成$f[i][j]+=f[i-1][i-j]$
1 #include<cstdio> 2 #define N (4209) 3 int n,p,f[2][N]; 4 int main() 5 { 6 scanf("%d%d",&n,&p); 7 f[1][1]=1; 8 for (int i=2; i<=n; ++i) 9 for (int j=1; j<=i; ++j) 10 f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][i-j])%p; 11 printf("%d\n",f[n&1][n]*2%p); 12 }
原文：https://www.cnblogs.com/refun/p/10165058.html