QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673969 | #9489. 0100 Insertion | professor_panda | TL | 1ms | 3792kb | C++14 | 1.5kb | 2024-10-25 12:37:58 | 2024-10-25 12:37:59 |
Judging History
answer
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long LL;
LL MOD = 998244353;
int main() {
int N;
cin >> N;
vector<char> S(N);
for (int i = 0; i < N; i++) cin >> S[N- 1 - i];
if (S[0] == '1' || S[1] == '1' || S[N - 1] == '1') {
cout << 0 << endl;
return 0;
}
// m[A][B][C]: A = (# of 0) - 3*(# of 1) + N / 4, B = A - min preA, C = 0 or 1
vector<vector<vector<int>>> m(N+1, vector<vector<int>>(N/2+1, vector<int>(2, 0)));
m[2+N/4][2][0] = 1;
for (int pos = 2; pos <N;pos++) {
vector<vector<vector<int>>> mp(N+1, vector<vector<int>>(N/2+1, vector<int>(2, 0)));
for (int a = 0; a <= N; a++) {
for (int b = 0; b <= N/2; b++) {
for (int c = 0; c < 2; c++) {
int t = m[a][b][c];
if (S[pos] != '1' && a+1 <= N && b+1 <= N/2) {
mp[a+1][b+1][0] += t;
mp[a+1][b+1][0] %= MOD;
}
if (S[pos] != '0' && c == 0 && b > 1 && a-3 >= 0) {
mp[a-3][max(b-3, 0)][1] += t;
mp[a-3][max(b-3, 0)][1] %= MOD;
}
}
}
}
swap(m, mp);
}
LL ans = 0;
for (int b = 0; b <= N/4; b++) {
ans += m[N/4][b][0];
ans %= MOD;
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3464kb
input:
8 0??0?100
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
4 ?10?
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
28 ???????????0???0??????1???0?
output:
2023
result:
ok "2023"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
4 ????
output:
1
result:
ok "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
8 11111111
output:
0
result:
ok "0"
Test #6:
score: -100
Time Limit Exceeded
input:
500 ????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...