QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54089#1882. DrunkardssyksykCCCWA 3ms3728kbC++141.1kb2022-10-06 20:47:452022-10-06 20:47:50

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:47:50]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3728kb
  • [2022-10-06 20:47:45]
  • 提交

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], f[N][N << 1];

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[0][n] = 1;
	for(int i = 1; i <= n; i++) {
		if(a[n - i + 1] == 1) {
			f[i][n] = 1;
			for(int j = n + 1; j <= n + i; j++) {
				f[i][j] = (((ll)p * f[i-1][j] + (ll)(1-p) * f[i-1][j-1]) % MOD + MOD) % MOD;
			}
			for(int j = n - i; j <= n - 1; j++) {
				f[i][j] = f[i - 1][j];
			}
		} else {
			f[i][n] = 1;
			for(int j = n - i; j <= n - 1; j++) {
				f[i][j] = (((ll)p * f[i-1][j] + (ll)(1-p) * f[i-1][j+1]) % MOD + MOD) % MOD;
			}
			for(int j = n + 1; j <= n + i; j++) {
				f[i][j] = f[i - 1][j];
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i <= n * 2; 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: 3ms
memory: 3652kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3728kb

input:

5 50
-1 1 -1 -1 -1

output:

952869610

result:

wrong answer 1st numbers differ - expected: '17015529', found: '952869610'