NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214012	#2662. 折跃	a_sad_soul	100	5601ms	195956kb	C++11	739b	2024-11-14 22:41:55	2024-11-14 23:11:16

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,a,b,k;
const int mod = 1e9+7;
int f[5005][5005];
int pre[5005];

signed main(){
    cin>>n>>a>>b>>k;
    f[a][0]=1;
    for(int i=1;i<=n;++i)pre[i]=(pre[i-1]+f[i][0])%mod;
    for(int K=1;K<=k;++K){
        for(int i=1;i<=n;++i){
            if(i==b)continue;
            if(i<b)f[i][K]=pre[i-1];
            else f[i][K]=(pre[n]-pre[i]+mod)%mod;
            int d=abs(b-i)-1;
            d/=2;
            if(i<b)f[i][K]=(f[i][K]+pre[i+d]-pre[i]+mod)%mod;
            else f[i][K]=(f[i][K]+pre[i-1]-pre[i-1-d]+mod)%mod;
        }
        for(int i=1;i<=n;++i)pre[i]=(pre[i-1]+f[i][K])%mod;
    }
    printf("%d\n",pre[n]);
    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 0ms

memory: 1640kb

input:

98 18 22 94

output:

27076018

result:

ok single line: '27076018'

Test #2:

score: 10

Accepted

time: 0ms

memory: 1632kb

input:

95 94 73 92

output:

748455277

result:

ok single line: '748455277'

Test #3:

score: 10

Accepted

time: 616ms

memory: 183948kb

input:

4674 2740 4172 4983

output:

454585991

result:

ok single line: '454585991'

Test #4:

score: 10

Accepted

time: 796ms

memory: 195956kb

input:

4981 813 4046 4994

output:

226418975

result:

ok single line: '226418975'

Test #5:

score: 10

Accepted

time: 703ms

memory: 180860kb

input:

4595 3757 519 4810

output:

194357577

result:

ok single line: '194357577'

Test #6:

score: 10

Accepted

time: 670ms

memory: 192864kb

input:

4902 277 2317 4821

output:

641852228

result:

ok single line: '641852228'

Test #7:

score: 10

Accepted

time: 616ms

memory: 177768kb

input:

4516 1607 639 4990

output:

973001631

result:

ok single line: '973001631'

Test #8:

score: 10

Accepted

time: 645ms

memory: 189772kb

input:

4823 1127 3840 4648

output:

431104558

result:

ok single line: '431104558'

Test #9:

score: 10

Accepted

time: 809ms

memory: 194232kb

input:

4937 3261 2918 4817

output:

638296884

result:

ok single line: '638296884'

Test #10:

score: 10

Accepted

time: 746ms

memory: 186688kb

input:

4744 135 2414 4828

output:

30641258

result:

ok single line: '30641258'