#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e6+20,mod = 1e9+7,inf = 1e9+10,maxm = 1e6;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k >>= 1;
}
return z;
}
int sos[N][2];
map<ll,int> mp;
ll pw[40];
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
int l,q;
cin >> l >> q;
pw[0] = 1;
rep(i,1,l) pw[i] = 3*pw[i-1];
string s;
cin >> s;
int n = s.size();
rep(i,0,n)
sos[i][1] = sos[i][0] = (s[i]-'0');
repr(j,l-1,0){
repr(i,n-1,0){
if (i&(1 << j))
sos[i][1] += sos[i-(1 << j)][1];
repr(j,l-1,0){
rep(i,0,n){
if (i&(1 << j) == 0)
sos[i][0] += sos[i+(1 << j)][0];
}
}
while (q--){
string t;
cin >> t;
ll jam = 0;
reverse(t.begin(),t.end());
int t0 = 0,t2 = 0,t1 = 0,mask = 0;
vector<int> ve;
rep(i,0,l){
if (t[i] == '1'){
t1++;
jam += pw[i];
mask += (1 << i);
}
else if (t[i] == '0') t0++;
else{
t2++;
jam += 2*pw[i];
}
}
if (mp.find(jam) != mp.end()){
cout << mp[jam] << endl;
continue;
}
if (t2 < 7){
rep(i,0,l) if (t[i] == '?') ve.pb(i);
int y = (1 << t2);
int ans = 0;
rep(j,0,y){
int sum = mask;
rep(k,0,t2)
if (j&(1 << k))
sum += (1 << ve[k]);
ans += (s[sum]-'0');
}
cout << ans << endl;
mp[jam] = ans;
continue;
}
if (t1 <= t0){
rep(i,0,l){
if (t[i] == '1') ve.pb(i);
if (t[i] == '?') mask += (1 << i);
}
int y = (1 << t1),ans = 0;
rep(i,0,y){
int cnt = 0,sum = mask;
rep(j,0,t1){
if ((1 << j)&i){
sum -= (1 << ve[j]);
cnt ^= 1;
}
}
if (cnt) ans -= sos[sum][1];
else ans += sos[sum][1];
}
cout << ans << endl;
mp[jam] = ans;
continue;
}
rep(i,0,l)
if (t[i] == '0')
ve.pb(i);
int y = (1 << t0),ans = 0;
rep(i,0,y){
int cnt = 0,sum = mask;
rep(j,0,t0)
if ((1 << j)&i){
sum += (1 << ve[j]);
cnt ^= 1;
}
if (cnt) ans -= sos[sum][0];
else ans += sos[sum][0];
}
cout << ans << endl;
mp[jam] = ans;
}
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:52:28: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
52 | if (i&(1 << j) == 0)
| ~~~~~~~~~^~~~
snake_escaping.cpp:132:1: error: expected '}' at end of input
132 | }
| ^
snake_escaping.cpp:46:18: note: to match this '{'
46 | repr(j,l-1,0){
| ^
snake_escaping.cpp:132:1: error: expected '}' at end of input
132 | }
| ^
snake_escaping.cpp:35:11: note: to match this '{'
35 | int main(){
| ^
