#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,int>
const int mxN = (1 << 20) + 5;
const int mod = 1e9 + 7;
using namespace std;
int sos[mxN][2][2];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
cin >>n>>q;
string s;
cin>>s;
for(int i = 0;i < n;i++){
for(int mask = 0;mask < (1 << n);mask++){
if(!i){
sos[mask][0][0] = s[mask] - '0';
if(mask &1) sos[mask][0][0] += s[mask - 1] - '0';
sos[mask][0][1] = s[mask] - '0';
if(mask &1 == 0) sos[mask][0][1] += s[mask + 1] - '0';
continue;
}
sos[mask][i &1][0] = sos[mask][(i - 1)&1][0];
sos[mask][i &1][1] = sos[mask][(i - 1)&1][1];
if(mask >> i & 1) sos[mask][(i)&1][0] += sos[mask - (1 << i)][(i - 1)&1][0];
else sos[mask][i &1][1] += sos[mask + (1 << i)][(i - 1)&1][1];
}
}
while(q--){
string a;
cin >>a;
reverse(a.begin(),a.end());
int Qcnt = 0, Ocnt = 0, Icnt = 0;
for(auto x : a){
if(x == '?') Qcnt++;
else if(x == '1') Icnt++;
else Ocnt++;
}
int ans = 0;
if(min({Qcnt,Ocnt,Icnt}) == Qcnt){
// printf("? small\n");
for(int mask = 0;mask < (1 << Qcnt);mask++){
int cnt = 0;
int num = 0;
int i = 0;
for(auto x : a){
if(x == '?') {
if(mask >> cnt & 1) num += (1 << i);
cnt++;
}
if(x == '1') num += (1 << i);
i++;
}
ans += s[num] - '0';
}
}else if(min({Qcnt,Ocnt,Icnt}) == Icnt){
// printf("1 small\n");
for(int mask = 0; mask < (1 << Icnt);mask++){
int cnt = 0;
int num = 0;
int i = 0;
for(auto x : a){
if(x == '1') {
if(mask >> cnt & 1) num += (1 << i);
cnt++;
}
if(x == '?') num += (1 << i);
i++;
}
if(Icnt &1 == __builtin_popcount(mask) &1) ans += sos[num][(n - 1)&1][0];
else ans -= sos[num][(n - 1)&1][0];
}
}else{
for(int mask = 0; mask < (1 << Ocnt);mask++){
// printf("0 small\n");
int cnt = 0;
int num = 0;
int i = 0;
for(auto x : a){
if(x == '0') {
if(mask >> cnt & 1) num += (1 << i);
cnt++;
}
if(x == '1') num += (1 << i);
// if(x == '?') num += (1 << i);
i++;
}
if(0 == __builtin_popcount(mask) & 1) ans += sos[num][(n - 1)&1][1];
else ans -= sos[num][(n - 1)&1][1];
}
}
cout<<ans<<'\n';
}
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:24:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
24 | if(mask &1 == 0) sos[mask][0][1] += s[mask + 1] - '0';
| ~~^~~~
snake_escaping.cpp:74:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
74 | if(Icnt &1 == __builtin_popcount(mask) &1) ans += sos[num][(n - 1)&1][0];
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:92:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
92 | if(0 == __builtin_popcount(mask) & 1) ans += sos[num][(n - 1)&1][1];
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
