QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54094#1882. DrunkardssyksykCCCWA 58ms120512kbC++14973b2022-10-06 20:59:272022-10-06 20:59:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 20:59:28]
  • 评测
  • 测评结果:WA
  • 用时:58ms
  • 内存:120512kb
  • [2022-10-06 20:59:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N = 5005, MOD = 998244353;
inline int inv(int a) {
	int res = 1, p = MOD - 2;
	while(p) {
		if(p & 1) res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		p >>= 1;
	}
	return res;
}

int n, p, a[N], g[N][N << 1], *f[N];

int main() {
	scanf("%d %d", &n, &p);
	p = (ll)p * inv(100) % MOD;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		f[i] = g[i] + n+1;
	}
	f[0] = g[0] + n+1;
	f[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		if(a[n - i + 1] == 1) {
			for(int j = -i; j <= i; j++) {
				f[i][j] = (((ll)p * f[i-1][j] + (ll)(1-p) * f[i-1][j-1]) % MOD + MOD) % MOD;
			}
		} else {
			for(int j = -i; j <= i; j++) {
				f[i][j] = (((ll)p * f[i-1][j] + (ll)(1-p) * f[i-1][j+1]) % MOD + MOD) % MOD;
			}
		}
		f[i][0] = 1;
	}
	ll ans = 0;
	for(int i = -n; i <= n; i++) {
		ans += f[n][i];
	}
	printf("%lld\n", ans * inv(n * 2 + 1) % MOD);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3724kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3876kb

input:

5 50
-1 1 -1 -1 -1

output:

17015529

result:

ok 1 number(s): "17015529"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

5 50
-1 1 -1 1 1

output:

680621150

result:

ok 1 number(s): "680621150"

Test #4:

score: 0
Accepted
time: 3ms
memory: 3816kb

input:

10 50
1 1 1 1 1 -1 -1 -1 1 1

output:

812744705

result:

ok 1 number(s): "812744705"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

10 50
-1 -1 1 1 -1 -1 1 -1 -1 -1

output:

158575275

result:

ok 1 number(s): "158575275"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3824kb

input:

15 65
1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 -1 1

output:

553313087

result:

ok 1 number(s): "553313087"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

15 65
-1 -1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1

output:

140408188

result:

ok 1 number(s): "140408188"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

10 7
1 1 1 1 1 1 1 1 1 1

output:

375530019

result:

ok 1 number(s): "375530019"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

10 73
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

289966217

result:

ok 1 number(s): "289966217"

Test #10:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

10 0
1 1 -1 1 1 1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #11:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

10 0
1 1 1 -1 1 1 1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #12:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

10 0
-1 1 1 1 -1 1 -1 -1 1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #13:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

10 0
-1 -1 -1 -1 -1 -1 1 -1 1 -1

output:

332748118

result:

ok 1 number(s): "332748118"

Test #14:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

10 0
1 1 1 1 1 1 -1 1 1 1

output:

570425345

result:

ok 1 number(s): "570425345"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3896kb

input:

10 0
-1 -1 -1 1 1 1 -1 1 -1 1

output:

475354454

result:

ok 1 number(s): "475354454"

Test #16:

score: 0
Accepted
time: 2ms
memory: 3836kb

input:

10 0
-1 1 1 1 1 -1 -1 1 -1 1

output:

95070891

result:

ok 1 number(s): "95070891"

Test #17:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

10 100
-1 1 -1 1 1 -1 -1 -1 -1 -1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #18:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

10 100
1 1 1 1 1 1 -1 1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #19:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

10 100
-1 -1 -1 -1 1 1 -1 -1 1 1

output:

617960790

result:

ok 1 number(s): "617960790"

Test #20:

score: 0
Accepted
time: 2ms
memory: 3820kb

input:

10 27
1 -1 -1 1 -1 -1 1 -1 -1 1

output:

89502877

result:

ok 1 number(s): "89502877"

Test #21:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

10 27
1 1 -1 1 -1 1 1 -1 -1 1

output:

602378374

result:

ok 1 number(s): "602378374"

Test #22:

score: -100
Wrong Answer
time: 58ms
memory: 120512kb

input:

5000 25
1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 -1 -1 ...

output:

185220320

result:

wrong answer 1st numbers differ - expected: '961556565', found: '185220320'