ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185071 | #2662. 折跃 | wosile | 100 | 2422ms | 98868kb | C++ | 677b | 2023-09-21 09:16:27 | 2023-09-21 12:23:14 |
answer
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,a,b,k;
int dp[5005][5005];
int l[5005],r[5005];
int main(){
scanf("%d%d%d%d",&n,&a,&b,&k);
dp[0][a]=1;
for(int i=1;i<=n;i++){
int d=abs(i-b);
l[i]=max(1,i-d+1);
r[i]=min(n,i+d-1);
}
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++)if(j!=b){
int v=dp[i-1][j];
dp[i][l[j]]=(dp[i][l[j]]+v)%mod;
dp[i][j]=(dp[i][j]-v)%mod;
dp[i][j+1]=(dp[i][j+1]+v)%mod;
dp[i][r[j]+1]=(dp[i][r[j]+1]-v)%mod;
}
for(int j=1;j<=n;j++)dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
}
int sum=0;
for(int i=1;i<=n;i++)sum=(sum+dp[k][i])%mod;
printf("%d",(sum+mod)%mod);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1616kb
input:
98 18 22 94
output:
27076018
result:
ok single line: '27076018'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1604kb
input:
95 94 73 92
output:
748455277
result:
ok single line: '748455277'
Test #3:
score: 10
Accepted
time: 294ms
memory: 98652kb
input:
4674 2740 4172 4983
output:
454585991
result:
ok single line: '454585991'
Test #4:
score: 10
Accepted
time: 321ms
memory: 98868kb
input:
4981 813 4046 4994
output:
226418975
result:
ok single line: '226418975'
Test #5:
score: 10
Accepted
time: 306ms
memory: 95272kb
input:
4595 3757 519 4810
output:
194357577
result:
ok single line: '194357577'
Test #6:
score: 10
Accepted
time: 334ms
memory: 95488kb
input:
4902 277 2317 4821
output:
641852228
result:
ok single line: '641852228'
Test #7:
score: 10
Accepted
time: 283ms
memory: 98792kb
input:
4516 1607 639 4990
output:
973001631
result:
ok single line: '973001631'
Test #8:
score: 10
Accepted
time: 308ms
memory: 92108kb
input:
4823 1127 3840 4648
output:
431104558
result:
ok single line: '431104558'
Test #9:
score: 10
Accepted
time: 295ms
memory: 95412kb
input:
4937 3261 2918 4817
output:
638296884
result:
ok single line: '638296884'
Test #10:
score: 10
Accepted
time: 281ms
memory: 95624kb
input:
4744 135 2414 4828
output:
30641258
result:
ok single line: '30641258'