#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
//#define mp make_pair
#define ll long long
//#define int ll
//#define double long double
const ll INF=1e18,N=(1<<20)+5;
int dp[N][2],a[N];
void solve(){
int n,q;cin>>n>>q;
string s;cin>>s;
for(int i=0;i<(1<<n);i++) a[i]=(s[i]-'0');
for(int i=0;i<(1<<n);i++) dp[i][0]=dp[i][1]=a[i];
for(int i=0;i<n;i++){
for(int mask=0;mask<(1<<n);mask++){
if(mask&(1<<i)) dp[mask][0]+=dp[mask^(1<<i)][0];
else dp[mask][1]+=dp[mask^(1<<i)][1];
}
}
while(q--){
string st;cin>>st;reverse(all(st));
int z=0,o=0,u=0;
for(int i=0;i<st.size();i++){
if(st[i]=='?') u++;
else if(st[i]=='0') z++;
else o++;
}
int sum=0,ans=0;
vector<int> tmp;
if(u<=6){
for(int i=0;i<n;i++){
if(st[i]=='1') sum+=(1<<i);
if(st[i]=='?') tmp.pb(1<<i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum;
for(int j=0;j<tmp.size();j++){
if(i&(1<<j)) tmpsum+=tmp[j];
}
ans+=a[tmpsum];
}
}
else if(o<=6){
for(int i=0;i<n;i++){
if(st[i]=='1' || st[i]=='?') sum+=(1<<i);
if(st[i]=='1') tmp.pb(1<<i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum,c=0;
for(int j=0;j<tmp.size();j++){
if(i&(1<<j)){
tmpsum^=(tmp[j]);
c++;
}
}
if(c%2) ans-=dp[tmpsum][0];
else dp[tmpsum][0];
}
}
else{
for(int i=0;i<n;i++){
if(st[i]=='1') sum+=(1<<i);
if(st[i]=='0') tmp.pb(1<<i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum,c=0;
for(int j=0;j<tmp.size();j++){
if(!(i&(1<<j))){
tmpsum^=(tmp[j]);
c++;
}
}
if(c%2) ans-=dp[tmpsum][1];
else ans+=dp[tmpsum][1];
}
}
cout<<ans<<endl;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t--)
solve();
}
Compilation message
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<st.size();i++){
| ~^~~~~~~~~~
snake_escaping.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
snake_escaping.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
snake_escaping.cpp:63:22: warning: statement has no effect [-Wunused-value]
63 | else dp[tmpsum][0];
| ~~~~~~~~~~~~^
snake_escaping.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
