题目大意
一栋楼有 \(n\) 层，初始位置在 \(a\) 层，你可以移动到的 \(y\) 层满足 \(\left|x-y\right|<\left|x-b\right|\)。不可以走到 \(b\) 层或留在原地，问一共走 \(k\) 次，有多少种走法。
思路
考虑简单的 DP。
记 \(dp_{i,j}\) 表示走到第 \(i\) 层，走了 \(j\) 次的方案数，\(l,r\) 分别是能够走到第 \(i\) 层的下界和上界，显然有：
\[dp_{i,j}=\sum_{k=l}^{r}dp_{k,j-1} \left[k \neq i \right]
\]
这个时间复杂度肯定爆炸，所以考虑前缀和优化。
记 $$\operatorname{sum}{i,j}=\sum^i dp_{k,j}$$
这样我们刚才的转移方程就可以变成这样：
\[dp_{i,j}=\operatorname{sum}_{r,j-1}-\operatorname{sum}_{l-1,j-1}-dp_{i,j-1}
\]
时间复杂度没问题了。
考虑空间，这道题需要开 long long，如果开两个二维的 long long 数组会炸空间。但由于本题有取模，我们可以考虑在计算过程中将变量转为 long long。
也可以选择滚动数组，观察状态转移方程，显然走 \(j\) 次的方案数只与走 \(j-1\) 次的方案数有关，可以滚掉，实测空间不到 1MB。
Code
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
int n,k,a,b;
int dp[5050][5050],sum[5050][5050];
// dp[i][j]：走到 i 用了 j 步的方案数
// sum：前缀和优化
signed main() {
cin >> n >> a >> b >> k;
if(a > b) {
n -= b;
a -= b;
}
else {
a = b - a;
n = b - 1;
}
// 只能在 B 层的一侧活动
// 可以直接把 B 层当做 0 层，方便计算
dp[a][0] = 1;
for(int i = a;i <= n; i++)
sum[i][0] = 1;
for(int i = 1;i <= k; i++) {
for(int j = 1;j <= n; j++)
dp[j][i] = ((long long)sum[n][i - 1] - (long long)sum[j >> 1][i - 1] - (long long)dp[j][i - 1] + 2ll * Mod) % Mod;
for(int j = 1;j <= n; j++)
sum[j][i] = ((long long)sum[j - 1][i] + (long long)dp[j][i]) % Mod;
}
cout << sum[n][k];
return 0;
}