如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
考虑 $\text{dp}$。
状态转移方程
我们定义 $f_{i,j}$ 为走到第 $i$ 层，共走了 $j$ 次的方案数，容易得到转移方程：
\[f_{i,j}=\sum\limits_{k=down}^{up} f_{k,j-1}\ [k\ne i]\]其中 $down$ 为能走到 $i$ 层的下界，$up$ 为上界。
时间复杂度 $O(n^2k)$，显然无法 $\text{A}$ 掉此题。这时，有经验的 $\text{OIer}$ 就会发现，这是可以用前缀和优化的。我们设 $s_{i,j}=\sum\limits_{k=1}^if_{k,j}$，得到新的转移方程：
\[f_{i,j}=s_{up,j-1}-s_{down-1,j-1}-f_{i,j-1}\]时间复杂度 $O(nk)$，可以 $\text{AC}$。
一些细节
显然，由于 $\mid x-y\mid <\mid x-b\mid $ 的限制，你只能在 $b$ 的一侧运动，那么，我们可以将 $b$ 层当做 $0$ 层。
if(a>b) n-=b,a-=b;
else n=b-1,a=b-a;
这样，我们就可以快速的求出 $up$ 和 $down$ 了，$up=n$，$down=\lfloor\frac i 2\rfloor+1$。
初始化：$f_{a,0}=1$
我们注意到，$j$ 次的方案数只依赖于 $j-1$ 次，所以我们可以采用滚动数组对空间进行优化。
代码
#include<cstdio> //for printf,scanf
#include<algorithm> //for min
int const mod=1000000007;
long long n,k,a,b,f[5010],s[5010];
int main(){
scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
if(a>b) n-=b,a-=b;
else n=b-1,a=b-a;
f[a]=1;
for(int i=a;i<=n;i++)s[i]=1;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++) f[j]=(s[n]-s[j>>1]-f[j]+mod+mod)%mod;
for(int j=1;j<=n;j++) s[j]=(s[j-1]+f[j])%mod;
}
printf("%lld",s[n]);
return 0;
}