QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54089 | #1882. Drunkards | syksykCCC | WA | 3ms | 3728kb | C++14 | 1.1kb | 2022-10-06 20:47:45 | 2022-10-06 20:47:50 |
Judging History
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'