NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213918 | #2662. 折跃 | x_add_b | 100 | 3002ms | 196436kb | C++11 | 1.2kb | 2024-11-14 19:05:22 | 2024-11-14 23:01:10 |
answer
#include<bits/stdc++.h>
namespace IO
{
template<typename Type>
void read(Type &x){
char ch=getchar();
x=0;bool f=0;
while(ch<'0'||ch>'9')
f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')
x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();
x=f?-x:x;
}
}
using namespace std;
#define LL long long
#define N 5005
#define MOD 1000000007
int n,a,b,k;
LL dp[N][N];
LL ans;
int main()
{
IO::read(n);IO::read(a);IO::read(b);IO::read(k);
dp[0][a]=1;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
int dist=abs(j-b)-1;
int L=max(j-dist,1),R=min(j+dist,n);
if(R<b||L>b){
(dp[i][L]+=dp[i-1][j])%=MOD;
(dp[i][j]-=dp[i-1][j])%=MOD;
(dp[i][j+1]+=dp[i-1][j])%=MOD;
(dp[i][R+1]-=dp[i-1][j])%=MOD;
}else{
int t1=j,t2=b;
if(t1>t2) swap(t1,t2);
(dp[i][L]+=dp[i-1][j])%=MOD;
(dp[i][t1]-=dp[i-1][j])%=MOD;
(dp[i][t1+1]+=dp[i-1][j])%=MOD;
(dp[i][t2]-=dp[i-1][j])%=MOD;
(dp[i][t2+1]+=dp[i-1][j])%=MOD;
(dp[i][R+1]-=dp[i-1][j])%=MOD;
}
}
for(int j=1;j<=n;j++)
(dp[i][j]+=dp[i][j-1])%=MOD;
}
for(int i=1;i<=n;i++)
(ans+=dp[k][i])%=MOD;
printf("%lld",(ans+MOD)%MOD);
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1608kb
input:
98 18 22 94
output:
27076018
result:
ok single line: '27076018'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1592kb
input:
95 94 73 92
output:
748455277
result:
ok single line: '748455277'
Test #3:
score: 10
Accepted
time: 374ms
memory: 196000kb
input:
4674 2740 4172 4983
output:
454585991
result:
ok single line: '454585991'
Test #4:
score: 10
Accepted
time: 410ms
memory: 196436kb
input:
4981 813 4046 4994
output:
226418975
result:
ok single line: '226418975'
Test #5:
score: 10
Accepted
time: 335ms
memory: 189240kb
input:
4595 3757 519 4810
output:
194357577
result:
ok single line: '194357577'
Test #6:
score: 10
Accepted
time: 362ms
memory: 189664kb
input:
4902 277 2317 4821
output:
641852228
result:
ok single line: '641852228'
Test #7:
score: 10
Accepted
time: 348ms
memory: 196276kb
input:
4516 1607 639 4990
output:
973001631
result:
ok single line: '973001631'
Test #8:
score: 10
Accepted
time: 420ms
memory: 182904kb
input:
4823 1127 3840 4648
output:
431104558
result:
ok single line: '431104558'
Test #9:
score: 10
Accepted
time: 401ms
memory: 189516kb
input:
4937 3261 2918 4817
output:
638296884
result:
ok single line: '638296884'
Test #10:
score: 10
Accepted
time: 352ms
memory: 189940kb
input:
4744 135 2414 4828
output:
30641258
result:
ok single line: '30641258'
