This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
int n, q;
cin >> n >> q;
string s;
cin >> s;
int full = (1<<n)-1;
vector<int> v(full+1);
for(int i = 0; i <= full; i++){
v[i] = s[i]-'0';
}
vector<int> f(full+1, 0), g(full+1, 0);
for(int mask = 0; mask <= full; mask++){
f[mask] = v[mask];
g[mask] = v[mask];
}
for(int i = 0; i < n; i++){
for(int mask = 0; mask <= full; mask++){
if(mask&(1<<i)) f[mask] += f[mask^(1<<i)];
}
for(int mask = full; mask >= 0; mask--){
if(!(mask&(1<<i))) g[mask] += g[mask^(1<<i)];
}
}
for(int i = 1; i <= q; i++){
string s;
cin >> s;
reverse(s.begin(), s.end());
int A, B, C;
A = B = C = 0;
int mask0 = 0, mask1 = 0, maskc = 0;
vector<int> a, b, c;
for(int i = 0; i < n; i++){
if(s[i] == '0'){
A++;
a.push_back(i);
}
if(s[i] == '1'){
B++;
b.push_back(i);
mask0 += (1<<i);
}
if(s[i] == '?'){
C++;
c.push_back(i);
mask1 += (1<<i);
}else{
maskc += (1<<i)*(s[i]-'0');
}
}
int mn = min({A, B, C});
int res = 0;
if(mn == A){
for(int mask = 0; mask < (1<<A); mask++){
int nmask = mask0;
for(int i = 0; i < A; i++){
if(mask&(1<<i)){
nmask += (1<<a[i]);
}
}
if(__builtin_popcount(mask)&1){
res -= g[nmask];
}else{
res += g[nmask];
}
}
cout << res << "\n";
continue;
}
if(mn == B){
for(int mask = 0; mask < (1<<B); mask++){
int nmask = mask1;
for(int i = 0; i < B; i++){
if(!(mask&(1<<i))){
nmask += (1<<b[i]);
}
}
if(__builtin_popcount(mask)&1){
res -= f[nmask];
}else{
res += f[nmask];
}
}
cout << res << "\n";
continue;
}
if(mn == C){
for(int mask = 0; mask < (1<<C); mask++){
int nmask = maskc;
for(int i = 0; i < C; i++){
if(mask&(1<<i)){
nmask += (1<<c[i]);
}
}
res += v[nmask];
}
cout << res << "\n";
continue;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |