前言：不说废话，野狼disco牛逼就完事了（网易云和b站绝对共享cookie
这题喵啊.....好多解法慢慢写吧...
1.一种优秀且优雅的组合数解法
首先发现一个性质，先下降和先上升序列一样多，只要把每个点取反就可以，所以我们可以只计算一种
例如我们计算先下降的序列，考虑往后加入$i$，那么一定是加到奇数位置，左右只要和$i$组合起来合法就可以，若加入$j$位置，那么左边可以放$j-1$个，右面可以放$i-j$个，答案乘上$f[j-1]*f[i-j]$，注意这里其实相当于是把数字离散化了，所以还要考虑数字分配问题，把$i-1$个数选$j-1$个分给左边，乘上$c[i-1][j-1]$，卡空间滚动数组求组合数
抄的代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=4209; ll f[maxn],c[2][maxn],p,n; int main(){ scanf("%d%d",&n,&p);c[0][0]=c[1][0]=f[0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++){ if(j&1)(f[i]+=(f[j-1]*f[i-j]%p)*(c[(i-1)&1][j-1]%p))%=p; c[i&1][j]=(c[(i-1)&1][j]+c[(i-1)&1][j-1]%p)%p; } printf("%lld",2*f[n]%p); }
2.有点难想的
三个性质：1.先下降数列等于先上升数列
2.具有对称性即把数列反向仍然合法
3.不好看出来的：在一个波动数列中，若两个 i 与 i+1 不相邻，那么我们直接交换这两个数字就可以组成一个新的波动数列 例如52314->42315
设$f[i][j]$为$1-i$第一个数为$j$且先下降的方案数，答案为$sum_{j=1}^{n} f[n][j]$
由性质三可知如果$j$与$j-1$不相邻时以$j$开头和以$j-1$开头的方案数一样，$j$和$j-1$不相邻的情况，先赋值$f[i][j]=f[i][j-1]$
接下来处理$j$和$j-1$相邻的情况，这样确定了后面那个是$j-1$，只要知道$j-1$开头的先上升序列数量即可，注意这里也相当于把数字离散化了，只是相对大小所以直接加没影响，求先上升序列数量需要用性质1取反一下$f[i][j]+=f[i-1][(i-1+1)-(j-1)]$
综上$f[i][j]=f[i-1][j-1]+f[i-1][i-j+1]$