分析
本来以为是纯组合数的题，但我找不到规律，然后就发现全网都是dp的解法
我们可以设 dp[i][j] 表示 i 个数组成的 开头为 j 且 j 为波峰的排列种数
然后我们经过思考之后就不难发现组成的序列会有以下的几条性质
-
一条序列具有对称性，将其前后调换位置后任满足题意
-
如果序列中 x 与 x+1 不相邻，则将二者交换位置后任然满足题意
为了便于理解，我们来简单的证明一下性质二
如果 x 是波峰，那他相邻的两个一定小于 x+1；
如果 x 是波谷，且 x+1 与 x 不相邻，那他相邻的两个最小是 x+2 和 x+3，一定大于 x+1
-
一条序列的连续子序列任满足题意
根据这三条性质，我们就可以推出转移方程
dp[i][j] += dp[i-1][(i-1)-(j-1)+1] % p;
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4300;
ll dp[2][N], n, p;
int main(){
ll x = 0;
scanf("%lld%lld",&n, &p);
dp[0][2] = 1;
for(int i=3; i<=n; i++){
x ^= 1;
for(int j=2; j<=i; j++){
dp[x][j] = (dp[x][j-1] + dp[x^1][i-j+1]) % p;
}
}
ll res = 0;
for(int i=2; i<=n; i++){
res = (res + dp[x][i]) % p;
}
res = (res * 2 % p + p) % p;
printf("%lld",res);
return 0;
}