[CEOI2016] kangaroo
其实就是给你一个\(p_1,p_n\)确定，其余未知的排列，求有多少个合法的排列，满足一个数要么比他相邻的两边都大，要么比他相邻的两边都小。
我们若是依次考虑每\(p_{1,2,\cdots ,n}\)，由于他的取值还和后面有关，我们不好考虑，考虑依次将\(i=1,2,\cdots,n\)填入当前的序列。
设\(dp_{i,j}\)表示现在填到了第\(i\)个数，填出来了\(j\)个块的方案数。（每一块相当于是在排列上连续的一段，但需要注意的是，我们并不关心这一段的具体位置）。
先考虑\(i=s/t\)的情况：
很明显，他们要么是会加入最左边/最右边的块，要么是单独在最左边/最右边作为一个块，所以：
\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1} \]其他情况下，我们分情况考虑：
- 若他把两个块合并起来，由于之前块的每一个数都比他小，所以明显可以，则\(f_{i,j}\leftarrow f_{i-1,j+1}\times j\)（之前的\(j+1\)个块中有\(j\)个空隙，可以填入任意一个）。
- 他加入一个块，那么此时他旁边的那个肯定小于它，但未来加入的肯定大于他，不合法。
- 若他单独开一个块，很明显接下来插入他两边的都比他大，则有\(j-1+1=j\)个位置，但是需要注意的是，若他比\(s\)大，则不能放到最左边（同\(s\)靠一起），比\(t\)大同理，则\(f_{i,j}\leftarrow f_{i-1,j-1}\times (j-[i>s]-[i>t])\)
注意到这样子我们构造出来的每一段都是如：小->大->小->大->小 这样的形式的，所以保证了dp式子的正确性（主要是第一个情况）。
初始状态为\(f_{1,1}=1\)，最终答案为\(f_{n,1}\)
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
inline int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=2e3+5,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,s,t;
int f[N][N];
signed main(){
n=rd(),s=rd(),t=rd();
f[1][1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(i==s||i==t) f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
else{
f[i][j]+=f[i-1][j+1]*j%mod;
f[i][j]+=f[i-1][j-1]*(j-(i>s)-(i>t))%mod;
f[i][j]%=mod;
}
}
}
printf("%lld\n",f[n][1]);
return 0;
}