欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1925
题意概括
给出n，n<=4200，问1~n这些数的排列中，有多少满足一下性质：
性质：对于一个数，满足它的相邻数都大于或者小于它。
答案mod P
题解
一道明摆着的动归题。
我们用dp[i][j]表示长度为i的序列（数字<=i），最终数为j的方案数。
我们只考虑开始的时候下降的情况，因为开始的时候上升的情况数是一样的，最后只要乘2就可以了。如果要我证明，那么只需要把开始下降的所有方案中的每一个数x更改成n+1-x就满足了。
然后考虑转移
如果接下来是上升，那么接下来填的数字x一定要比j大。那么你会说数字重复了。实际上我们只需要把前面>=x的数字都+1就可以了。也就是说，实际上前面的方案只是数字的排名。
那么方程就很明显了。
下降也差不多的。
看代码。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=4200+5;
int n,mod,dp[2][N];
int main(){
scanf("%d%d",&n,&mod);
memset(dp,0,sizeof dp);
dp[0][1]=1;
int x=0,y;
for (int i=2;i<=n;i++){
y=x,x^=1;
memset(dp[x],0,sizeof dp[x]);
int sum=0;
if (i%2==0)
for (int j=i-1;j>=1;j--)
sum=(sum+dp[y][j])%mod,dp[x][j]=(dp[x][j]+sum)%mod;
else
for (int j=1;j<i;j++)
sum=(sum+dp[y][j])%mod,dp[x][j+1]=(dp[x][j+1]+sum)%mod;
}
int ans=0;
for (int i=1;i<=n;i++)
ans=(ans+dp[x][i])%mod;
printf("%d",ans*2%mod);
return 0;
}