题解$^2$

阿巴阿巴阿巴……

看题解后

抖动序列就是一大一小交替循环的序列。
若 $\large x$ 与 $\large x+1$ 不相邻（ $\large x$ 为山峰高度），则交换 $\large x$ 与 $\large x+1$ 后依旧是抖动序列。所以 $$\Large f{i}{,}{j}=f{i}{,}{{j-1}}$$
$\Large f{_i}{_,}{_j}$ 就是从 $1$ 到 $i$ ，末尾为 $j$ 时的序列个数。
因为如果 $x$ 与 $x+1$ 相邻，则一定不能交换。如果 $x$ 与 $x+1$ 不相邻，则其他数一定大于 $x+1$ 或小于 $x$ 。 $x$ 与 $x+1$ 就像一个中间值，不管怎么换，都满足抖动序列定义。
并且将序列从中间某个地方断开，再将头尾结合，仍然满足抖动序列，即将 $[1,n]$ 的序列从 $k$ 处断开，则 $[k+1,n]$ 与 $[1,k]$ 合并之后仍然是抖动序列。
还有，一个抖动数列的子序列也是一个抖动序列。
所以转移方程为 $$\Large f{i}{,}{j}=f{{i-1}}{,}{{i-j+1}}+f{{i}}{,}{_{j-1}}$$ 其中 $j \leq i$ 。

优化

但是还可以优化一下，因为当算到 $i$ 时， $i-1$ 以前的就全都没有用了。所以可以滚动数组优化一下。

代码

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define endl '\n'
#define N (10000010)
#define int long long
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;
int n,m,t,P;
int x,y,k,L,R,tot,lon;
int len,prime[700010];//,phi[N];//线性筛欧拉函数
bitset<N>vis;
int f[2][4211];
long long inv[N];//乘法逆元
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
int e[N],siz[N];
long long qpow(long long x,int b,int P=P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}//O(log(b))
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=(a/b*x);
    return d;
}//O(max(a,b))
int ola(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)ans=ans/i*(i-1);
        for(;n%i==0;n/=i);
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}//O(sqrt(n))
void eular(int n)//欧拉筛
{
    //memset(vis,0,sizeof(vis));
    //phi[1]=1;
    for(int i(2);i<=n;++i)
    {
        if(!vis[i])
            prime[++len]=i;//,phi[i]=(i-1);
        for(int j(1);j<=len&&i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            /*
            if(!(i%prime[j]))
                {phi[i*prime[j]]=(phi[i]*prime[j]);break;}
            else phi[i*prime[j]]=(phi[i]*(prime[j]-1));
            */
        }
    }
}//O(n)
void niyuan1(int n)//乘法逆元
{
    inv[1]=1;
    for(int i(2);i<=n;++i)inv[i]=((P-P/i)*inv[P%i])%P;
}//O(n)4
int inv_it(int a)//O(log(a))
{
    int d(exgcd(a,P,x,y));
    return (x%P+P)%P;
}
int C(int n,int m,int P=P)
{return (m>n)?0:(e[n]*qpow((e[m]*e[n-m])%P,P-2))%P;}
int lucas(int n,int m,int P=P)
{return (!m)?1:(C(n%P,m%P)*lucas(n/P,m/P))%P;}
void init()
{
    n=read(),P=read();
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    init();
    int lss(1);
    f[1][1]=1;
    for(int i(2);i<=n;++i)
    {
        lss^=1;
        for(int j(1);j<=i;++j)
            f[lss][j]=(f[lss^1][i-j+1]+f[lss][j-1])%P;
    }
    for(int i(1);i<=n;++i)
        tot=(tot+f[lss][i])%P;
    write((tot<<1)%P,' ');
    flush();
    return 0;
}