QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#604809 | #9174. Game Design | fosov | WA | 1ms | 3828kb | C++14 | 1.1kb | 2024-10-02 14:01:37 | 2024-10-02 14:01:39 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define N 5050
int main() {
#ifdef TEST
freopen("zz.in", "r+", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while (t --) {
string s; cin >> s;
int n = s.length();
int m = 0;
for (auto c : s) m += c == '1';
assert(m <= n);
vector<vector<ll>> dp(n+10, vector<ll>(n+10, 0));
for (int j = 0; j <= m; ++ j) dp[0][j] = j % 2 == m % 2 ? 1 : -1;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j <= m; ++ j) {
if (s[i-1] == '1') {
if (j) dp[i][j-1] = (dp[i][j-1] + j * dp[i-1][j] % MOD) % MOD;
dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
} else {
dp[i][j] = (dp[i][j] + j * dp[i-1][j] % MOD) % MOD;
}
}
}
cout << dp[n][0] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
4 0101 1010010010001010 11111 10100100011000010010101001001001
output:
3 0 44 393298077
result:
ok 4 number(s): "3 0 44 393298077"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 01 11 10 00
output:
1 1 0 0
result:
ok 4 number(s): "1 1 0 0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
8 011 110 100 000 010 101 111 001
output:
2 0 0 0 0 1 2 1
result:
ok 8 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
16 0111 0110 0000 1001 1100 0011 0100 1110 1011 0001 1000 0010 1111 0101 1010 1101
output:
9 0 0 1 0 6 0 0 6 1 0 0 9 3 0 3
result:
ok 16 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
32 01100 10010 11011 10100 00100 01010 10000 01111 11000 01001 00101 00011 11001 11111 10001 00000 00111 11101 11010 10110 10111 01101 10011 11100 01110 00001 01000 10101 01011 00010 00110 11110
output:
0 0 22 0 0 0 0 44 0 3 7 14 3 44 1 0 33 11 0 0 33 11 14 0 0 1 0 7 22 0 0 0
result:
ok 32 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
64 001000 011100 101100 001101 011110 100000 000000 001111 000101 110111 010001 101111 001001 011111 111100 010011 100010 000001 010110 111111 111101 110101 111010 011010 110110 101000 101110 010010 011011 010000 100110 001010 101010 100111 100100 100101 110000 010111 011000 110011 000100 101001 111...
output:
0 0 0 39 0 0 0 212 15 159 3 212 7 265 0 50 0 1 0 265 53 25 0 0 0 0 0 0 106 0 0 0 0 117 0 15 0 159 0 50 0 7 0 0 25 53 3 117 30 11 39 78 0 0 30 0 0 1 0 11 78 106 0 0
result:
ok 64 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
128 0111100 0110000 1010010 1001001 1010110 0011101 0100100 1100110 0110101 1001110 0101110 1111011 0100101 0111110 1001011 0110010 1111000 0101111 1101011 1001000 1110100 1000011 1001111 1101000 0100000 0010010 1100000 1011000 0100111 1001101 1010111 0111101 1110011 0101011 0001110 0010100 0011110 ...
output:
0 0 0 15 0 245 0 0 117 0 0 618 53 0 262 0 0 1236 362 0 0 62 980 0 0 0 0 0 543 131 735 309 234 362 0 0 0 1545 0 11 7 1236 0 170 25 15 0 3 490 0 735 0 0 0 0 106 0 618 0 1854 85 393 0 0 106 0 7 31 0 62 39 0 31 0 53 0 0 927 0 0 927 39 0 0 170 0 543 980 393 0 0 25 0 0 0 262 11 0 1 0 0 0 3 0 131 309 0 53 ...
result:
ok 128 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
256 01101111 10001000 01111011 01100010 10101111 00100101 11111101 01010000 00111010 01101001 10001101 00101011 00100000 11000111 01001010 10111100 01000001 11001101 01110111 00101000 00100001 01101010 10101101 01101000 11111100 11000110 11001110 00011111 01010101 11101010 10110010 11111000 11011000...
output:
8476 0 4238 0 7028 177 2119 0 0 117 423 1626 0 1779 0 0 3 593 6357 0 7 0 813 0 0 0 0 8785 387 0 0 0 0 1097 0 0 0 0 0 0 0 0 0 0 0 0 3514 0 0 0 0 0 53 0 11 109 2194 126 0 423 5580 0 0 12714 0 2119 10595 2066 0 85 3099 0 0 0 0 0 0 8785 490 0 354 1186 554 1342 11 0 0 1269 39 387 0 0 0 0 25 671 0 0 2066 ...
result:
ok 256 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
512 011101111 100101011 001000111 000000011 111011100 111110010 000011111 001100011 001101100 110001101 100010001 000010000 010110100 111001110 010110010 000101010 000111100 000110011 001111010 000001100 010010001 100110010 101010000 110110101 010100101 000111000 000111001 011000111 011010011 000011...
output:
66748 7106 7827 254 0 0 48825 2194 0 1885 31 0 0 0 0 0 0 4650 0 0 53 0 0 2971 799 0 1097 9999 4366 0 671 28518 85554 11 0 23662 0 0 9094 0 0 0 0 569 5761 11831 4547 0 42777 0 0 59155 3759 0 15 7763 0 9094 5942 0 1033 0 813 9765 3770 1331 133496 3993 0 0 71295 0 53 0 31052 6123 5218 0 15526 0 0 0 999...
result:
ok 512 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
500 1000111011 1110100001 0111111011 1110001101 0111100101 0110000101 0110100111 0001101011 1000001011 1001000111 1010011001 0110001001 1100011011 1110100101 1110000101 0001001111 1110111001 0011101010 1110001001 0110111111 0111101111 1011010001 1001010111 1001011101 1110110011 1101011111 1100110001...
output:
106426 117 296658 10489 9403 1013 90825 62978 8238 33639 2609 501 52542 4483 1013 169404 9403 0 501 889974 593316 529 127053 42351 39678 553585 593 188678 129523 221 2325 0 245 24543 39110 741645 221 0 11831 2026 22267 129523 388569 39 0 10790 1334961 12839 18341 7383 6975 24543 85 9481 3 459555 234...
result:
ok 500 numbers
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 3664kb
input:
50 1100100010011000000010000010100000000000000000100000100000000000110100000000011010110010010000000001 0001000000010000000010000000000001000001000001011011100001001000101000000000100000000001000000100001 00100000000000000000000001010000000010010000001000100000011010000000110010000000100010000010001...
output:
-792535493 923855108 -78382513 547941024 630835913 963096460 -440641518 220618001 647925838 0 0 -950588092 460024445 0 838886692 191295282 499427902 294750324 -344228761 0 -404982331 -290710752 -840301194 -69601516 696324035 -753004834 -189530276 -286303736 -250344521 -879710485 -119824089 806102755...
result:
wrong answer 1st numbers differ - expected: '205708860', found: '-792535493'