前言
写这篇题解的原因是这道题提供了一种新的 dp 思路——插入 dp。
题意
给定一个长为 \(n\) 的数轴，一只袋鼠在上面要从 \(s\) 跳到 \(t\)，跳跃过程中，每次跳跃方向必须与上一次相反，求方案数。
分析
拿到这个题其实还是蛮蒙的，但是如果我们转化（抽象）一下题意，就会发现这道题可以看作：
求以 \(s\) 开头，以 \(t\) 结尾的排列数，其中对于任一排列，都有排列中每个元素 \(a_i\) 满足 \(a_i>a_{i-1}\) 且 \(a_i>a_{i+1}\)，或 \(a_i<a_{i-1}\) 且 \(a_i<a_{i+1}\)。
这里的每个排列，其实就是跳跃顺序。
这样，我们就可以考虑从小到大，向已有的排列中加入数。设 \(dp_{i, j}\) 表示将有 \(i\) 个数的排列划分成 \(j\) 段的方案总数。那么，对于第 \(i\) 个元素，有三种去向：
1.连接两段元素
因为是按照从小到大插入，故一定满足插入的数大于两端的数。如果前 \(i-1\) 个数划分成 \(j+1\) 段，则有 \(j\) 个位置可以插入，插入后段数少 \(1\) 。于是有
\[dp_{i, j}+=dp_{i-1, j+1} \times j
\]
2.单独成段，插入原排列
这种情况下，如果原序列有 \(j-1\) 段，那么新的这一段就有 \(j\) 个位置可以放置。但是要注意一点，就是当 \(s\) 和 \(t\) 放入排列中后，排列首和尾将无法再放入，因此需要特殊处理；同样，对于 \(s\) 和 \(t\)，插入的时候只能在首或尾，最多只能连接一段。
于是有
\[dp_{i, j}+=dp_{i-1, j-1} \times(j-(i>s)-(i>t))
\]
3.插入排列中任意一段充当首或尾
我们发现，这样插入之后，必然会在之后把比它大的数放在旁边，这样就无法满足条件了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2020, mod = 1e9+7;
void add(int &a, int b){
a = (1ll*a+1ll*b)%mod;
}
int dp[N][N];
int n, s, t;
int main(){
scanf("%d%d%d", &n, &s, &t);
dp[1][1] = 1;//第一个数分成1段有一种方案。
for(int i = 2; i<=n; ++i){
for(int j = 1; j<=i; ++j){
if((i ^ s)&&(i ^ t)){
add(dp[i][j], 1ll*dp[i-1][j+1]*j%mod);
add(dp[i][j], 1ll*dp[i-1][j-1]*(j-(i>s)-(i>t))%mod);
} else{
add(dp[i][j], dp[i-1][j-1]);
add(dp[i][j], dp[i-1][j]);//特殊处理s和t。
}
}
}
printf("%d\n", dp[n][1]);
system("pause");
return 0;
}