「CF480C」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 y must 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).
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).
Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).
|
1 |
5 2 4 1 |
|
1 |
2 |
|
1 |
5 2 4 2 |
|
1 |
2 |
|
1 |
5 3 4 1 |
|
1 |
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.
题解
f[i][j]表示第i步走到j的方案数
然后用个前缀和dp一下。。。我开了5000w的longlong发现爆内存。。。
其实直接改int就行了，我还搞了个滚动数组 T T
傻逼题搞了半天太悲伤
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,a,b,K; ll f[2][5005],s[2][5005]; int main() { n=read();a=read();b=read();K=read(); f[0][a]=1; for(int i=a;i<=n;i++)s[0][i]=1; for(int i=1;i<=K;i++) { for(int j=1;j<=n;j++) if(j!=b) { if(j<b) f[i&1][j]=s[(i-1)&1][(b+j-1)>>1]-f[(i-1)&1][j]; else f[i&1][j]=s[(i-1)&1][n]-s[(i-1)&1][(b+j)>>1]-f[(i-1)&1][j]; f[i&1][j]%=mod; } for(int j=1;j<=n;j++) { s[i&1][j]=s[i&1][j-1]+f[i&1][j]; s[i&1][j]%=mod; } memset(s[(i-1)&1],0,sizeof(s[(i-1)&1])); memset(f[(i-1)&1],0,sizeof(f[(i-1)&1])); } printf("%d",(s[K&1][n]%mod+mod)%mod); return 0; } |
OI 课件=>
