#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
int f[1<<20],g[1<<20];
string s;
ll L;
ll q;
int n(const int &x)
{
ll ans=0;
for(int i=0;i<L;i++)
{
if((x>>i&1)==0)
{
ans+=1<<i;
}
}
return ans;
}
ll a[maxN];
void solve()
{
cin >> L >> q;
cin >> s;
for(int i=0;i<(1<<L);i++)
{
f[i]=s[i]-'0';
}
for(int i=0;i<(1<<L);i++)
{
g[i]=s[n(i)]-'0';
}
for(int i = 0;i < L; ++i) for(int mask = 0; mask < (1<<L); ++mask){
if((mask & (1<<i))==0)
f[mask] += f[mask^(1<<i)];
}
for(int i = 0;i < L; ++i) for(int mask = 0; mask < (1<<L); ++mask){
if((mask & (1<<i))==0)
g[mask] += g[mask^(1<<i)];
}
ll ct,so;
while(q--)
{
string t;
cin >> t;
ll cnt[3];
for(int i=0;i<L;i++)
{
if(t[i]=='0') cnt[0]++;
else if(t[i]=='1') cnt[1]++;
else cnt[2]++;
}
ll mn=inf;
for(int i=0;i<3;i++) mn=min(mn,cnt[i]);
if(cnt[0]==mn)
{
ct=0,so=0;
for(int i=0;i<L;i++)
{
if(t[i]=='0')
{
a[ct]=L-i-1;
ct++;
}
else if(t[i]=='1')
{
so+=1<<(L-i-1);
}
}
ll ass=0,bs;
for(int i=0;i<(1<<ct);i++)
{
bs=0;
for(int j=0;j<ct;j++)
{
if(i>>j&1)
{
bs+=1<<(a[j]);
}
}
if(__builtin_popcount(i)&1) ass-=f[so+bs];
else ass+=f[so+bs];
}
cout << ass << '\n';
}
else if(cnt[1]==mn)
{
ct=0,so=0;
for(int i=0;i<L;i++)
{
if(t[i]=='1')
{
a[ct]=L-i-1;
ct++;
}
else if(t[i]=='0')
{
so+=1<<(L-i-1);
}
}
ll ans=0,bs;
for(int i=0;i<1<<ct;i++)
{
bs=0;
for(int j=0;j<ct;j++)
{
if(i>>j&1)
{
bs+=1<<(a[j]);
}
}
if(__builtin_popcount(i)&1) ans-=g[so+bs];
else ans+=g[so+bs];
}
cout << ans << '\n';
}
else
{
so=0,ct=0;
for(int i=0;i<L;i++)
{
if(t[i]=='1')
{
so+=1<<(L-i-1);
}
else if(t[i]=='?') a[ct]=L-i-1,ct++;
}
ll ans=0;
for(int i=0;i<1<<ct;i++)
{
ll bs=0;
for(int j=0;j<ct;j++)
{
if(j>>i&1)
{
bs+=1<<a[j];
}
}
ans+=s[bs+so]-'0';
}
cout << ans << '\n';
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
