#ifdef ONPC
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef ONPC
#pragma GCC target("avx")
#pragma GCC target("popcnt")
#define cerr if (false) cerr
#endif
using namespace std;
#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
return uniform_int_distribution<ll>(l, r)(gen64);
}
template<class T>
bool umin(T &a, const T &b) {
return (a > b ? a = b, true : false);
}
template<class T>
bool umax(T &a, const T &b) {
return (a < b ? a = b, true : false);
}
const int mod = 998244353;
ll mult(ll a, ll b) {
return (a * b) % mod;
}
template<class T>
void add(T &a, const T &b) {
a = (a + b) % mod;
}
const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;
const int maxn = 1e5 + 10, B = 10, P = 59049;
ll b[P][1 << B];
void solve() {
int l, q;
cin >> l >> q;
int n = (1 << l);
string s;
cin >> s;
vector<int> a(n);
auto convert = [&](const vector<int> &d, int mask) {
int res = 0;
for (int i = 0; i < B; ++i) {
if (mask >> i & 1) {
res = 3 * res + 2;
} else {
res = 3 * res + d[i];
}
}
return res;
};
for (int i = 0; i < n; ++i) {
a[i] = s[i] - '0';
ll l = i >> B;
vector<int> d;
ll x = i % (1 << B);
while (x > 0) {
d.push_back(x & 1);
x >>= 1;
}
while (d.size() < B) {
d.push_back(0);
}
for (int mask = 0; mask < (1 << B); ++mask) {
int r = convert(d, mask);
b[r][l] += a[i];
}
}
while (q--) {
string s;
cin >> s;
reverse(all(s));
while (s.size() < B) {
s.push_back(B);
}
vector<int> d(B);
int mask = 0, left = 0;
for (int i = 0; i < B; ++i) {
d[i] = (s[i] == '1' ? 1 : 0);
if (s[i] == '?') {
mask |= (1 << i);
}
}
int r = convert(d, mask);
mask = 0;
for (int i = 0; i < l - B; ++i) {
if (s[i + B] == '?') {
mask |= (1 << i);
}
if (s[i + B] == '1') {
left |= (1 << i);
}
}
ll ans = 0;
for (int s = 0; s <= mask; s = ((s | ~mask) + 1) & mask) {
ans += b[r][left | s];
if (s == mask) break;
}
cout << ans << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
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... |