题目大意：

　　若数列$\{A_i\}$为$1\sim n(n\le4200)$的一个排列，求满足对于任意$1<i<n$都有$A_i>A_{i-1}$且$A_i>A_{i+1}$或$A_i<A_{i-1}$且$A_i<A_{i+1}$的$\{A_i\}$的方案数。

思路：

　　用$f[i][j]$表示$A$的前$i$项为$1\sim i$的排列，$A_1=j>A_2$的方案数。

　　若$j-1\ne A_2$，则直接交换$j$和$j-1$，数列依然满足条件，贡献$f[i][j-1]$的方案数。

　　若$j-1=A_2$，则贡献为$A$的前$i-1$项为$1\sim i-1$的排列，$A_1=j-1<A_2$的方案数。不难发现对于数列$A$，若将每一个$A_i$都替换成$n-A_i+1$，数列依然满足条件。则贡献的方案数等同于$f[i-1][i-j+1]$。

　　则得出状态转移方程为$f[i][j]=f[i][j-1]+f[i-1][i-j+1]$。

1 #include
     
       2 #include
      
        3 inline int getint() { 4     register char ch; 5     while(!isdigit(ch=getchar())); 6     register int x=ch^'0'; 7     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 8     return x; 9 }10 const int N=4201;11 int f[2][N];12 int main() {13     const int n=getint(),mod=getint();14     f[0][2]=1;15     for(register int i=3;i<=n;i++) {16         for(register int j=2;j<=i;j++) {17             f[i&1][j]=(f[i&1][j-1]+f[!(i&1)][i-j+1])%mod;18         }19     }20     int ans=0;21     for(register int i=1;i<=n;i++) {22         (ans+=(f[n&1][i]*2)%mod)%=mod;23     }24     printf("%d\n",ans);25     return 0;26 }