解析
这个似乎并不好讲啊
设(f[i][j])表示有(i)座山,
最后一座山到达高度是(i)座中第(j)大的,
且最后一座山是山谷.
注意,(i)是代表有(i)座山,并不代表高度一定是(1)~(i).
(j)也是一个类似于离散化的东西.
然后我们考虑设(g[i][j]),
除了最后一座山是山峰以外其它的定义和(f[i][j])一样.
那么有式子(f[i][j]=sum_{k=j}^{i-1}g[i-1][k]).
在这里讲一下最大和最小值的问题,
最大值可以随便往大了取,
但考虑到前(i)座山的最后一座一定比前(i-1)座的小(因为是山谷),
所以最后一座是第(j)大那它前面一座在前(i-1)座山中的排名就不可能小于(j).
(可能表达有点不太清楚,感性理解下吧.)
还有一件显然的事,
如果有一个合法的方案,
那我们把每座山的高度(h_i)换成(n-h_i+1),方案依然合法(就是把山峰换成了山谷).
因此(g[i][j]=f[i][i-j+1]).
合并一下就变成了(f[i][j]=sum_{k=1}^{i-j}f[i-1][k]).
而这个相当于一个后缀和的东西.
因此DP式就是(f[i][j]=f[i][j+1]+f[i-1][i-j]).
用滚动数组优化下空间就行了.
#include <iostream>
#include <cstdio>
#include <cstring>
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
const int N=4301;
int n,Mod,f[2][N];
int ans=0;
int main(){
n=read();Mod=read();
f[1][1]=1;int now=1;
for(int i=2;i<=n;i++){
now^=1;memset(f[now],0,sizeof(f[now]));
for(int j=i-1;j;j--) f[now][j]=(f[now][j+1]+f[now^1][i-j])%Mod;
}
for(int i=1;i<=n;i++) ans=(ans+f[now][i])%Mod;
printf("%d
",(ans<<1)%Mod);
return 0;
}