#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int bits, queries;
cin >> bits >> queries;
int size = 1 << bits;
vector<int> base(size), sumSub(size), sumSup(size);
string tox;
cin >> tox;
for (int mask = 0; mask < size; mask++) {
base[mask] = tox[mask] - '0';
sumSub[mask] = base[mask];
sumSup[mask] = base[mask];
}
for (int b = 0; b < bits; b++) {
for (int mask = 0; mask < size; mask++) {
if (mask & (1 << b)) {
sumSub[mask] += sumSub[mask ^ (1 << b)];
} else {
sumSup[mask] += sumSup[mask ^ (1 << b)];
}
}
}
while (queries--) {
string pattern;
cin >> pattern;
reverse(pattern.begin(), pattern.end());
int maskZero = 0;
int maskOne = 0;
int maskAny = 0;
for (int i = 0; i < bits; i++) {
char c = pattern[i];
if (c == '0') maskZero |= 1 << i;
if (c == '1') maskOne |= 1 << i;
if (c == '?') maskAny |= 1 << i;
}
int result = 0;
int countAny = __builtin_popcount(maskAny);
int countOne = __builtin_popcount(maskOne);
int countZero= __builtin_popcount(maskZero);
if (countAny <= 6) {
result = base[maskOne];
for (int sub = maskAny; sub; sub = (sub - 1) & maskAny) {
result += base[sub | maskOne];
}
}
else if (countOne <= 6) {
result = 0;
for (int sub = maskOne; ; sub = (sub - 1) & maskOne) {
int parity = __builtin_parity(sub);
result += (parity ? -1 : 1) * sumSub[sub | maskAny];
if (sub == 0) break;
}
}
else {
result = 0;
for (int sub = maskZero; ; sub = (sub - 1) & maskZero) {
int parity = __builtin_parity(sub);
result += (parity ? -1 : 1) * sumSup[sub | maskOne];
if (sub == 0) break;
}
}
cout << result << "\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... |