UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185071#2662. 折跃wosile1002422ms98868kbC++677b2023-09-21 09:16:272023-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'