求1~n组成一个抖动序列的方案数
首先这种序列有一些非常妙妙但我发现不了的性质
1.对于一个抖动序列，如果i和i+1不相邻，则交换i和i+1，他还是个抖动序列
2.对于一个抖动序列，我把每个数拿n+1减一下（上下翻转），他还是个抖动序列，只不过波峰和波谷换了一下
3.对于一个抖动序列，我把它左右翻转，他还是个抖动序列
于是设f[i][j]是i个数中，排名为j的数在第一个位置、且它是波峰的方案数
那么答案就是$2\sum{f[N][i]}$（我把它翻一下不就有所有的第一个数作为波谷的情况了嘛）
然后有方程$f[i][j]=f[i][j-1]+f[i-1][j-1]$
考虑两种情况：
1.j和j-1不相邻，由性质1这种情况的f[i][j]就是f[i][j-1]
2.j和j-1相邻，也就是j-1在第二个位置，这种情况的f[i][j]就是f[i-1][j-1]，就是不看j，然后把剩下的i-1个数拎出来，那j-1的排名还是j-1
合起来就是上面的方程
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,f[][maxn],P; int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),P=rd();
f[][]=;
for(i=;i<=N;i++){
for(j=;j<=i;j++){
f[i&][j]=(f[i&][j-]+f[!(i&)][i-j+])%P;
}
}
int ans=;
for(i=;i<=N;i++)
ans+=f[N&][i],ans%=P;
printf("%d\n",ans*%P);
return ;
}