#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define fu(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fd(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; ++i)
#define el cout << "\n"
#define MAX_SIZE 1000005
#define LOG 21
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e15)
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {if (a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {if (a > b){a = b; return true;} return false;}
template <class T1, class T2>
void add(T1 &a, T2 b) {a += b; if (a >= MOD) a -= MOD;}
template <class T1, class T2>
void sub(T1 &a, T2 b) {a -= b; if (a < 0) a += MOD;}
template <class T>
void dup_shot(vector <T> &v) {
sort(ALL(v));
v.erase(unique(ALL(v)), (v).end());
}
int l, q;
ll sum[MASK(20) + 3][2];
// 0: super
// 1: sub
void init() {
cin >> l >> q;
fu(i, 0, MASK(l) - 1) {
char c; cin >> c;
sum[i][0] = sum[i][1] = (c - '0');
}
}
void run() {
fu(i, 0, l - 1) {
fu(mask, 0, MASK(l) - 1) if (BIT(mask, i)) sum[mask][1] += sum[mask ^ MASK(i)][1];
fd(mask, 0, MASK(l) - 1) if (!BIT(mask, i)) sum[mask][0] += sum[mask ^ MASK(i)][0];
}
while (q--) {
string s;
cin >> s;
reverse(ALL(s));
int mask0 = 0, mask1 = 0, mask2 = 0;
fu(i, 0, l - 1) {
if (s[i] == '0') mask0 += MASK(i);
if (s[i] == '1') mask1 += MASK(i);
if (s[i] == '?') mask2 += MASK(i);
}
if (__builtin_popcount(mask0) <= 6) {
ll res = 0;
for (int mask = mask0; mask >= 0; mask = (mask - 1) & mask0) {
if (__builtin_popcount(mask) & 1) res -= sum[mask + mask1][0];
else res += sum[mask + mask1][0];
if (mask == 0) break;
}
cout << res << "\n";
}
else if (__builtin_popcount(mask1) <= 6) {
ll res = 0;
for (int mask = mask0; mask >= 0; mask = (mask - 1) & mask1) {
if (__builtin_popcount(mask) & 1) res -= sum[MASK(l) - 1 - mask0 - mask][1];
else res += sum[MASK(l) - 1 - mask0 - mask][1];
if (mask == 0) break;
}
cout << res << "\n";
}
else {
ll res = 0;
for (int mask = mask2; mask >= 0; mask = (mask - 1) & mask2) {
res += sum[mask + mask1][1];
if (mask == 0) break;
}
cout << res << "\n";
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
clock_t start = clock();
run();
cerr << "\nTime run: " << clock() - start << " ms!\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
