#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int dp1[Mxn+10],dp0[Mxn+10],cost[Mxn+10],rdp0[mxn+10];
int32_t main(){
fastio
int n,q;cin>>n>>q;
string a;cin>>a;
for(int i=0;i<(1LL<<n);i++)cost[i]=dp1[i]=dp0[i]=(a[i]-'0');
for(int i=0;i<n;i++)for(int j=0;j<(1LL<<n);j++)if(j&(1LL<<i))dp1[j]+=dp1[j^(1LL<<i)];
for(int i=0;i<n;i++)for(int j=(1LL<<n)-1;j>=0;j--)if(!(j&(1LL<<i)))dp0[j]+=dp0[j+(1LL<<i)];
int root=sqrt(n);
root++;
auto change=[&](int x){
int k=0;
for(int i=0;i<n;i++)if(!(x&(1LL<<i)))k+=1LL<<i;
return k;
};
//for(int i=0;i<(1LL<<n);i++)rdp0[change(i)]=dp0[i];
while(q--){
cin>>a;
reverse(all(a));
int x=0,y=0;
vector<int>o,z,c;
int bro=0;
for(int i=0;i<n;i++){
if(a[i]=='1')x+=(1LL<<i),o.pb(i),y+=(1LL<<i);
else if(a[i]=='?')c.pb(i),bro+=(1LL<<i);
else z.pb(i);
}
int m=0;
int ans=0,g;
if(c.size()<=root){//5 tl
m=c.size();
for(int i=0;i<(1LL<<m);i++){
for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x-=(1LL<<c[j]);
ans+=cost[x];
for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x+=(1LL<<c[j]);
}
}
else if(o.size()<z.size()){
ans=dp1[x];
m=o.size();
for(int i=0;i<(1LL<<m)-1;i++){
int cnt=0;
for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x-=(1LL<<o[j]),cnt++;
if(cnt%2)ans-=dp1[x];
else ans+=dp1[x];
for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x+=(1LL<<o[j]);
}
/*
*/
}
else{
ans=dp0[y];
m=z.size();
for(int i=1;i<(1LL<<m);i++){
int cnt=0;
for(int j=0;j<m;j++)if((i&(1LL<<j)))y+=(1LL<<z[j]),cnt++;
if(cnt%2)ans-=dp0[y];
else ans+=dp0[y];
for(int j=0;j<m;j++)if((i&(1LL<<j)))y-=(1LL<<z[j]);
}
}
cout<<ans<<'\n';
//return 0;
//cout<<dp1[x]<<" "<<dp0[y]<<'\n';
}
}
/*
if cnt? <= sqrt(m) we can do (2^4)? bruteforce (maybe even 5)
else we can do sos dp and somehow remove the overcount
we can turn all ? into one and get sos of that bit
overcount when "1" bit that is originaly turned on switch to 0(for subset)
we can switch them off and subtract from the original answer so it cost 2^(cnt1){
we need to somehow do pie
starting from original answer-> if we turn off 1 bit
ans-(turn of x bit)-(turn of y bit)+(turn of x and y bit)
so if cnt%2==1 then we subtract
else we add back in
}
cnt1 can be at most 16,worst case is all 1 (2^16)
we can also do sos dp where 0 is now the "switchable" value
so if cnt0<cnt1 we take do from 0 dp else from 1
tc-> worst case q*(2^m)*m
pre com time is m*(2^m+1)
q*(x*(2^x)+(2^(m-x)/2))
*/
Compilation message
snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:68:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
68 | if(c.size()<=root){//5 tl
| ~~~~~~~~^~~~~~
snake_escaping.cpp:67:13: warning: unused variable 'g' [-Wunused-variable]
67 | int ans=0,g;
| ^
snake_escaping.cpp:49:7: warning: variable 'change' set but not used [-Wunused-but-set-variable]
49 | auto change=[&](int x){
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
