UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213962#2662. 折跃stawalr804379ms97728kbC++11629b2024-11-14 20:07:582024-11-14 23:05:19

answer

#include<bits/stdc++.h>
using namespace std;
const int mn=5005,mod=1e9+7;
int f[mn][mn];
int sum[mn];
int n,a,b,k;
int main()
{
    scanf("%d%d%d%d",&n,&a,&b,&k);
    for(int i=1;i<=n;i++)
    {
        if(i!=b)f[i][0]=1;
        sum[i]=sum[i-1]+f[i][0];
    }
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int dis=abs(j-b)-1;
            f[j][i]=((((sum[min(j+dis,n)]-sum[max(j-dis,1)-1])%mod+mod)%mod-f[j][i-1])%mod+mod)%mod;
        }
        for(int j=1;j<=n;j++)
        {
            sum[j]=(sum[j-1]+f[j][i])%mod;
        }
    }
    printf("%d",f[a][k]);
}

Details

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

Test #1:

score: 10
Accepted
time: 0ms
memory: 1620kb

input:

98 18 22 94

output:

27076018

result:

ok single line: '27076018'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1596kb

input:

95 94 73 92

output:

748455277

result:

ok single line: '748455277'

Test #3:

score: 10
Accepted
time: 736ms
memory: 92588kb

input:

4674 2740 4172 4983

output:

454585991

result:

ok single line: '454585991'

Test #4:

score: 0
Time Limit Exceeded

input:

4981 813 4046 4994

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

4595 3757 519 4810

output:


result:


Test #6:

score: 10
Accepted
time: 724ms
memory: 97048kb

input:

4902 277 2317 4821

output:

641852228

result:

ok single line: '641852228'

Test #7:

score: 10
Accepted
time: 666ms
memory: 89496kb

input:

4516 1607 639 4990

output:

973001631

result:

ok single line: '973001631'

Test #8:

score: 10
Accepted
time: 670ms
memory: 95500kb

input:

4823 1127 3840 4648

output:

431104558

result:

ok single line: '431104558'

Test #9:

score: 10
Accepted
time: 859ms
memory: 97728kb

input:

4937 3261 2918 4817

output:

638296884

result:

ok single line: '638296884'

Test #10:

score: 10
Accepted
time: 724ms
memory: 93952kb

input:

4744 135 2414 4828

output:

30641258

result:

ok single line: '30641258'