#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
string s;
int n, l, q;
const int p3[] = {1,3,9,27,81,243,729};
const int B1 = 6;
const int B2 = 20-B1;
const int N = p3[B1];
int pre[N][1<<B2], score[N][1<<B2];
int calc(string lol){
int p = 1, ans = 0, xd;
for(int i = 0; i < B1; i++){
if(lol[i]=='?') xd=2;
else xd = lol[i]-'0';
ans+=xd*p, p*=3;
}
return ans;
}
int calc(int lol){
int p = 1, ans = 0;
for(int i = 0; i < B1; i++)
ans+=(lol>>i&1)*p, p*=3;
return ans;
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> l >> q >> s; n = (1<<l);
if(l<B1){
for(int _ = 0; _ < q; _++){
string t; cin >> t;
reverse(all(t));
int cnt = 0;
for(int i = 0; i < n; i++){
int ok = 1;
for(int j = 0; j < l; j++)
ok&=(t[j]=='?' or (t[j]-'0')==(i>>j&1));
cnt+=ok*(s[i]-'0');
}
cout << cnt << "\n";
}
return 0;
}
l-=B1;
for(int mask = 0; mask < n; mask++){
int mask1 = calc(mask&((1<<B1)-1));
int mask2 = mask>>B1;
int sc = s[mask]-'0';
score[mask1][mask2]+=sc;
for(int t = mask2; ; t--,t&=mask2){
pre[mask1][t]+=sc; if(!t) break;
}
}
for(int mask = 0; mask < (1<<(B1*2)); mask++){
string t = "", t2 = "";
for(int i = 0; i < B1*2; i+=2){
int cur = mask>>i&1;
t+=(char)(cur+'0');
if(mask>>(i+1)&1) cur=2;
t2+=(char)(cur+'0');
}
int mask1 = calc(t);
int mask2 = calc(t2);
if(t==t2) continue;
for(int i = 0; i < (1<<l); i++){
pre[mask2][i]+=pre[mask1][i];
score[mask2][i]+=score[mask1][i];
}
}
for(int _ = 0; _ < q; _++){
string t; cin >> t; reverse(all(t));
int x = calc(t.substr(0,B1));
t = t.substr(B1);
int cnt = 0, ans = 0, xd2 = 0;
vector<int> pos, pos2;
pos.clear(); pos2.clear();
for(int i = 0; i < sz(t); i++){
if(t[i]=='?') pos.pb(i),cnt++;
else{
pos2.pb(i);
if(t[i]=='1') xd2+=1<<i;
}
}
if(cnt*2<=B2){
for(int mask = 0; mask < (1<<cnt); mask++){
int xd = 0;
for(int i = 0; i < cnt; i++)
if(mask>>i&1) xd+=1<<pos[i];
ans+=score[x][xd+xd2];
}
}
else{
cnt = sz(pos2); ans = pre[x][0];
for(int mask = 1; mask < (1<<cnt); mask++){
int num = __builtin_popcount(mask), xd=0;
for(int i = 0; i < cnt; i++)
if(mask>>i&1) xd+=(1<<pos2[i])*(t[pos2[i]]=='0');
ans+=(num%2?-1:1)*score[x][xd];
}
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
