This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int B = 13, N = 1<<20, SZ = pow(3, B);
int Q, dp[SZ], ans[N], id[N];
string A, inp;
short x[N], y[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> Q >> Q >> A;
A.resize(N, '0');
for(int i = 0; i < Q; ++i) {
cin >> inp;
reverse(begin(inp), end(inp));
inp.resize(20, '0');
for(int k = 0, p = 1; k < B; ++k, p *= 3)
id[i] += p * ((48 < inp[k]) + (62 < inp[k]));
for(int k = 0; k < 20-B; ++k) {
if(inp[k+B] == '?') y[i] |= 1<<k;
if(inp[k+B] == '1') x[i] |= 1<<k;
}
}
for(int s = 0; s < (1<<(20-B)); ++s) {
memset(dp, 0, sizeof dp);
for(int i = 0; i < (1<<B); ++i) {
int j = 0;
for(int k = 0, p = 1; k < B; ++k, p *= 3)
if(i & (1<<k)) j += p;
dp[j] += A[i | (s << B)] - '0';
}
for(int i = 1; i < SZ; ++i) {
int j = -1, pw = 1;
for(int k = 0, p = i; k < B; ++k, p /= 3, pw *= 3)
if((p % 3) > 1) j = k, k = B;
if(j >= 0)
pw /= 3, dp[i] = dp[i - pw] + dp[i - 2 * pw];
}
for(int i = 0; i < Q; ++i)
if(((x[i] ^ s) | y[i]) == y[i])
ans[i] += dp[id[i]];
}
for(int i = 0; i < Q; ++i)
cout << ans[i] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |