NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213979 | #2662. 折跃 | laiyishi | 100 | 1677ms | 196488kb | C++11 | 630b | 2024-11-14 20:59:46 | 2024-11-14 23:06:51 |
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a,b,k,dp[5005][5005],tt[5005][5005];
int main(){
scanf("%d%d%d%d",&n,&a,&b,&k);
dp[0][a]=1;
for(int i=1;i<=n;i++)tt[0][i]=tt[0][i-1]+dp[0][i];
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
int t=j;
if(j==b);
else if(j<b){
if((t&1)==(b&1))t--;
int p=(t+b-1)/2;
dp[i][j]=(tt[i-1][p]+mod-dp[i-1][j])%mod;
}else{
if((t&1)==(b&1))t++;
int p=(t+b+1)/2;
dp[i][j]=((tt[i-1][n]+mod-tt[i-1][p-1])%mod+mod-dp[i-1][j])%mod;
}
tt[i][j]=(tt[i][j-1]+dp[i][j])%mod;
}
}
printf("%d\n",tt[k][n]);
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 2012kb
input:
98 18 22 94
output:
27076018
result:
ok single line: '27076018'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1996kb
input:
95 94 73 92
output:
748455277
result:
ok single line: '748455277'
Test #3:
score: 10
Accepted
time: 151ms
memory: 196052kb
input:
4674 2740 4172 4983
output:
454585991
result:
ok single line: '454585991'
Test #4:
score: 10
Accepted
time: 201ms
memory: 196488kb
input:
4981 813 4046 4994
output:
226418975
result:
ok single line: '226418975'
Test #5:
score: 10
Accepted
time: 186ms
memory: 189292kb
input:
4595 3757 519 4810
output:
194357577
result:
ok single line: '194357577'
Test #6:
score: 10
Accepted
time: 191ms
memory: 189724kb
input:
4902 277 2317 4821
output:
641852228
result:
ok single line: '641852228'
Test #7:
score: 10
Accepted
time: 309ms
memory: 196328kb
input:
4516 1607 639 4990
output:
973001631
result:
ok single line: '973001631'
Test #8:
score: 10
Accepted
time: 238ms
memory: 182956kb
input:
4823 1127 3840 4648
output:
431104558
result:
ok single line: '431104558'
Test #9:
score: 10
Accepted
time: 232ms
memory: 189564kb
input:
4937 3261 2918 4817
output:
638296884
result:
ok single line: '638296884'
Test #10:
score: 10
Accepted
time: 169ms
memory: 190000kb
input:
4744 135 2414 4828
output:
30641258
result:
ok single line: '30641258'
