QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396666 | #1882. Drunkards | deepthought | ML | 0ms | 3972kb | C++23 | 3.0kb | 2024-04-22 23:26:52 | 2024-04-22 23:26:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <int MOD> struct modint{
static const int mod = MOD;
int v;
operator int() const {return v;}
modint():v(0) {}
modint(long long _v):v(int(_v%MOD)) {v += (v<0)*MOD;}
modint& operator+=(modint o) {if((v += o.v) >= MOD) v-= MOD; return *this;}
modint& operator-=(modint o) {if((v -= o.v) < 0) v+= MOD; return *this;}
modint& operator*=(modint o) {v = int((long long)v*o.v%MOD); return *this;}
modint& operator/=(modint o) {return *this *= inv(o);}
friend modint pow(modint a, long long p) {
modint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; } friend modint inv(modint a) {assert(a.v != 0); return pow(a, MOD-2);}
friend modint operator+(modint a, modint b) {return a += b;}
friend modint operator-(modint a, modint b) {return a -= b;}
friend modint operator*(modint a, modint b) {return a *= b;}
friend modint operator/(modint a, modint b) {return a /= b;}
};
using mint = modint<(int)998244353>;
int main() {
int n, pp;
cin >> n >> pp;
mint stay = (mint)pp * inv((mint)100);
mint move = (mint)(100 - pp) * inv((mint)100);
vector <int> arr(n + 1);
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
mint home_prob = inv(mint(2 * n + 1));
mint dp[2 * n + 1][2 * n + 1][2 * n + 1];
for(int i = 0; i < 2 * n + 1; i++){
for(int j = 0; j < 2 * n + 1; j++) {
for(int k = 0; k < 2 * n + 1; k++) {
dp[i][j][k] = 0;
}
}
dp[i][n][0] = home_prob;
}
// dp[home][idx][time]
mint answer = home_prob; // if home = n
dp[n][n][0] = 0;
for(int time = 1; time <= n; time++) {
for(int home = 0; home <= 2 * n; home++) {
for(int idx = 0; idx <= 2 * n; idx++) {
dp[home][idx][time] += dp[home][idx][time - 1] * stay;
if(idx > 0) {
if(arr[time] == 1) {
dp[home][idx][time] += dp[home][idx - 1][time - 1] * move;
}
}
if(idx < 2 * n) {
if(arr[time] == -1) {
dp[home][idx][time] += dp[home][idx + 1][time - 1] * move;
}
}
if(home == idx) {
// cout << idx << " " << dp[home][idx][time] << endl;
answer += dp[home][idx][time];
// if(home == 6 and idx == 6 and time == 2) cout << dp[home][idx][time] << endl;
// if(dp[home][idx][time] != 0) cout << dp[home][idx][time] << " home:" << home << " time:" << time << endl;
dp[home][idx][time] = 0;
}
}
}
}
cout << ((int)answer) << endl;
// cout << home_prob << endl;
// cout << "prob:" << (home_prob * stay * stay * move) << endl;
}
/*
d.in: 340310575
a.in: 702764025
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
2 28 1 1
output:
702764025
result:
ok 1 number(s): "702764025"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 50 -1 1 -1 -1 -1
output:
17015529
result:
ok 1 number(s): "17015529"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 50 -1 1 -1 1 1
output:
680621150
result:
ok 1 number(s): "680621150"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3884kb
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: 3656kb
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: 0ms
memory: 3972kb
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: 0ms
memory: 3900kb
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: 3888kb
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: 0ms
memory: 3656kb
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: 0ms
memory: 3652kb
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: 0ms
memory: 3600kb
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: 0ms
memory: 3892kb
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: 0ms
memory: 3600kb
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: 0ms
memory: 3588kb
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: 0ms
memory: 3652kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3652kb
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: 0ms
memory: 3888kb
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: 0ms
memory: 3648kb
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: 0ms
memory: 3856kb
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
Memory Limit Exceeded
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 ...