Riding in a Lift
Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.
Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y ≠ x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen ymust be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x - y| < |x - b|. After the lift successfully transports you to floor y, you write down number y in your notepad.
Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109 + 7).
Input
The first line of the input contains four space-separated integers n, a, b, k (2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b).
Output
Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).
Examples
5 2 4 1
2
5 2 4 2
2
5 3 4 1
0
Note
Two sequences p1, p2, ..., pk and q1, q2, ..., qk are distinct, if there is such integer j (1 ≤ j ≤ k), that pj ≠ qj.
Notes to the samples:
- In the first sample after the first trip you are either on floor 1, or on floor 3, because |1 - 2| < |2 - 4| and |3 - 2| < |2 - 4|.
- In the second sample there are two possible sequences: (1, 2); (1, 3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip.
- In the third sample there are no sought sequences, because you cannot choose the floor for the first trip.
sol：非常水的dp，直接转移是n3的，但是智障选手比方说我写了数据结构优化（树状数组），可以做到n2logn，但是还是TLE了，然后想了一会发现自己脑抽了，直接差分就是n2了
然后悲伤的T了两发
#include <bits/stdc++.h> using namespace std; typedef int ll; inline int read() { int s=0; bool f=0; char ch=' '; while(!isdigit(ch)) { f|=(ch=='-'); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(int x) { if(x<0) { putchar('-'); x=-x; } if(x<10) { putchar(x+'0'); return; } write(x/10); putchar((x%10)+'0'); return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar(' ') const int N=5005,Mod=1000000007; int n,a,b,m; int dp[N][N]; inline void Ad(int &x,int y) { x+=y; x-=(x>=Mod)?Mod:0; x+=(x<0)?Mod:0; } struct BIT { int S[N]; #define lowbit(x) ((x)&(-x)) inline void Init() { memset(S,0,sizeof S); } inline void Ins(int x,int Val) { for(;x<=n;x+=lowbit(x)) { Ad(S[x],Val); } } inline void Updata(int l,int r,int Val) { Ins(l,Val); Ins(r+1,-1*Val); } inline int Que(int x) { int Sum=0; for(;x>0;x-=lowbit(x)) { Ad(Sum,S[x]); } return Sum; } }T; int S[N]; int main() { int i,j,k; R(n); R(a); R(b); R(m); dp[a][0]=1; for(i=0;i<m;i++) { // T.Init(); for(j=1;j<=n;j++) if(dp[j][i]) { int oo=abs(j-b)-1; // if(max(1,j-oo)<=j-1) T.Updata(max(1,j-oo),j-1,dp[j][i]); // if(j+1<=min(n,j+oo)) T.Updata(j+1,min(n,j+oo),dp[j][i]); if(max(1,j-oo)<=j-1) { Ad(dp[max(1,j-oo)][i+1],dp[j][i]); Ad(dp[j-1+1][i+1],-1*dp[j][i]); } if(j+1<=min(n,j+oo)) { Ad(dp[j+1][i+1],dp[j][i]); Ad(dp[min(n,j+oo)+1][i+1],-1*dp[j][i]); } } for(j=1;j<=n;j++) Ad(dp[j][i+1],dp[j-1][i+1]); // for(j=1;j<=n;j++) dp[j][i+1]=T.Que(j); } int ans=0; for(i=1;i<=n;i++) Ad(ans,dp[i][m]); Wl(ans); return 0; } /* Input 5 2 4 1 Output 2 Input 5 2 4 2 Output 2 Input 5 3 4 1 Output 0 input 2222 1206 1425 2222 output 402572650 Input 5000 2500 1 5000 Output 898026985 */