UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213922#2662. 折跃one_zero_four_zero04029ms195964kbC++111.1kb2024-11-14 19:08:502024-11-14 23:01:35

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define mod 1000000007LL
using namespace std;

int N, A, B, K;
long long ans = 0;
long long dp[5005][5005];

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

	scanf("%d %d %d %d", &N, &A, &B, &K);
	dp[0][A] = 1;
	for (int i = 0; i < N; i ++){
		for (int j = 1; j <= N; j ++){
			// cout << i << " " << j << " " << dp[i][j] << ";;\n"; 
			if (j == B) continue;
			int st = j - abs(j - B) + 1;
			int en = j + abs(j - B) - 1;
			st = max(st, 1), en = min(en, N);
			// cout << st << " " << en << "[]\n";
			dp[i + 1][st] += dp[i][j];
			dp[i + 1][en + 1] -= dp[i][j];
			dp[i + 1][j] -= dp[i][j];
			dp[i + 1][j + 1] += dp[i][j];
			dp[i + 1][st] %= mod, dp[i + 1][en + 1] %= mod;
			dp[i + 1][j] %= mod, dp[i + 1][j + 1] %= mod;
		}
		for (int j = 1; j <= N; j ++){
			dp[i + 1][j] += dp[i + 1][j - 1]; // d_i -> a_i
			dp[i + 1][j] = ((dp[i + 1][j] % mod) + mod) % mod;
		}
	}
	for (int i = 1; i <= N; i ++){
		ans += dp[N][i];
		ans %= mod;
	}
	printf("%lld\n", ans % mod);

    return 0;
}

详细

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

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1660kb

input:

98 18 22 94

output:

192959578

result:

wrong answer 1st lines differ - expected: '27076018', found: '192959578'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 1644kb

input:

95 94 73 92

output:

586043573

result:

wrong answer 1st lines differ - expected: '748455277', found: '586043573'

Test #3:

score: 0
Wrong Answer
time: 460ms
memory: 183964kb

input:

4674 2740 4172 4983

output:

261204331

result:

wrong answer 1st lines differ - expected: '454585991', found: '261204331'

Test #4:

score: 0
Wrong Answer
time: 529ms
memory: 195964kb

input:

4981 813 4046 4994

output:

886358607

result:

wrong answer 1st lines differ - expected: '226418975', found: '886358607'

Test #5:

score: 0
Wrong Answer
time: 523ms
memory: 180872kb

input:

4595 3757 519 4810

output:

877838866

result:

wrong answer 1st lines differ - expected: '194357577', found: '877838866'

Test #6:

score: 0
Wrong Answer
time: 513ms
memory: 192872kb

input:

4902 277 2317 4821

output:

288428054

result:

wrong answer 1st lines differ - expected: '641852228', found: '288428054'

Test #7:

score: 0
Wrong Answer
time: 445ms
memory: 177780kb

input:

4516 1607 639 4990

output:

895336456

result:

wrong answer 1st lines differ - expected: '973001631', found: '895336456'

Test #8:

score: 0
Wrong Answer
time: 492ms
memory: 189788kb

input:

4823 1127 3840 4648

output:

27145610

result:

wrong answer 1st lines differ - expected: '431104558', found: '27145610'

Test #9:

score: 0
Wrong Answer
time: 538ms
memory: 194248kb

input:

4937 3261 2918 4817

output:

448951935

result:

wrong answer 1st lines differ - expected: '638296884', found: '448951935'

Test #10:

score: 0
Wrong Answer
time: 529ms
memory: 186696kb

input:

4744 135 2414 4828

output:

118551454

result:

wrong answer 1st lines differ - expected: '30641258', found: '118551454'