拿到这道题秒懂题意：波动序列。
然鹅不会打。想了一节课，想打纯组合数学，结果找不到规律。
想的是先假设拍出一个序列，然后交换其中的元素求组合，
无奈没啥规律可循，显然不能一口气求出来（我说的是我没办法，网上大佬们有的是办法……）
然后想dp，挨个插入，妄图一维dp走起，结果摔倒在地
然后我就不是人了。
^废话^
称n个数组成的波动数列为n阶波动数列。
我们设f[i][j]表示一个i阶波动数列首个数是j且为山峰的排列种数。
然后推一下状态转移方程。
仔细考虑一下，波动序列似乎有这么几个性质
性质一：一个波动序列的连续子序列仍然是波动序列。
性质二：若使一个波动序列排列中大于等于x的元素全部+1，序列仍然满足波动。
性质三：若一个波动序列的排列中x与x+1不相邻，那么交换二者，序列仍然满足波动。
性质四：一个[1,x]的波动序列一定可以对应到[y-x+1,y]的一个波动序列。
其实都是一些十分显然的性质。我们主要用到了性质一、三和四来搞我们的状态转移方程。
简单证明性质三（因为某大佬问我的时候在这个性质上稍微犹豫了一下～）
1.若x为波谷，由于x与x+1不相邻，则x两侧的波峰最低为x+2和x+3，交换后仍然满足波动序列。
2.若x为波峰，x两侧的波谷小于x，则必定小于x+1。所以交换后仍然满足波动序列。
证毕。
（^自己证哒^，有不当的地方请多多海涵并评论指出～谢谢大家～）
所以根据性质一，我们可以进行状态转移。（没错性质一是最费的……）
根据性质三，f[i][j]+=f[i][j-1]。（把+1和-1倒个个儿还是一样的……我是不是证翻了QAQ）这好说。
但我们只考虑了性质三中x与x+1不相邻的状态。
于是尝试把j掐掉。
我们发现，把波动序列最左边的j掐掉之后剩下了一个i-1阶的波动序列。
但是我们不能直接转移，现在最左边的变成了j-1。一切是那么顺利，可是j-1是波谷啊QAQ！！
波谷！！
那怎么办？没关系我们有性质四！
回顾一下性质四：一个[1,x]的波动序列一定可以对应到[y-x+1,y]的一个波动序列。
这是啥？这是救世主！
于是我们把所有的序列对应到i-j+1上，发现这东西瞬间变波峰。
（这需要证明吗QAQ，我懒啊～）
然后我们得到了另外一个状态转移：
f[i][j]+=f[i-1][(i-1)-(j-1)+1]。（别问我为什么变成i-1和j-1了 /糊脸）
完结撒花～
代码：
#include#include #include #include #define ll long long#define rint register intusing namespace std;ll n,mod,f[2][5005];signed main(){ ll now=0; scanf("%lld %lld",&n,&mod); f[now][2]=1; for(rint i=3;i<=n;i++) { now^=1; for(rint j=2;j<=i;j++) f[now][j]=(f[now][j-1]+f[now^1][i-j+1])%mod; } ll ans=0; for(rint i=2;i<=n;i++) ans=(ans+f[now][i])%mod; ans=(ans*2%mod+mod)%mod; printf("%lld\n",ans); return 0;}