#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20;
int cost[1 << MAX_N], sumDown[1 << MAX_N], sumUp[1 << MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
string c;
cin >> n >> q;
cin >> c;
for (int mask = 0; mask < (1 << n); mask++)
cost[mask] = sumDown[mask] = sumUp[mask] = c[mask] - '0';
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if ((mask >> i) & 1)
sumDown[mask] += sumDown[mask ^ (1 << i)];
}
}
for (int i = 0; i < n; i++) {
for (int mask = (1 << n) - 1; mask >= 0; mask--) {
if (!((mask >> i) & 1))
sumUp[mask] += sumUp[mask ^ (1 << i)];
}
}
for (int mask = (1 << n) - 1; mask >= 0; mask--)
printf("%d %d\n", mask, sumUp[mask]);
while (q--) {
string s;
cin >> s;
reverse(s.begin(), s.end());
vector<int> pq, p0, p1;
for (int i = 0; i < n; i++) {
if (s[i] == '?')
pq.push_back(i);
else if (s[i] == '0')
p0.push_back(i);
else
p1.push_back(i);
}
int ans = 0;
if ((int)p0.size() <= 6) {
int mask = 0;
for (int i = 0; i < n; i++)
mask += ((s[i] == '1') << i);
for (int fixed = 0; fixed < (1 << p0.size()); fixed++) {
int newMask = mask, cnt = 0;
for (int i = 0; i < (int)p0.size(); i++) {
if ((fixed >> i) & 1) {
cnt++;
newMask += (1 << p0[i]);
}
}
if (cnt % 2 == 0)
ans += sumUp[newMask];
else
ans -= sumUp[newMask];
}
} else if ((int)p1.size() <= 6) {
int mask = 0;
for (int i = 0; i < n; i++)
mask += ((s[i] != '0') << i);
for (int fixed = 0; fixed < (1 << p1.size()); fixed++) {
int newMask = mask, cnt = 0;
for (int i = 0; i < (int)p1.size(); i++) {
if ((fixed >> i) & 1) {
cnt++;
newMask -= (1 << p1[i]);
}
}
if (cnt % 2 == 0)
ans += sumDown[newMask];
else
ans -= sumDown[newMask];
}
} else {
int mask = 0;
for (int i = 0; i < n; i++)
mask += ((s[i] == '1') << i);
for (int fixed = 0; fixed < (1 << pq.size()); fixed++) {
int newMask = mask;
for (int i = 0; i < (int)pq.size(); i++) {
if ((fixed >> i) & 1)
newMask += (1 << pq[i]);
}
ans += cost[newMask];
}
}
cout << ans << "\n";
}
return 0;
}
# | 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... |