题目
题解
考虑暴力，用$N_c$表示字符$c$在询问字符串中出现的次数
- 可以$O(2^{N_?})$枚举$?$选什么
- 可以处理出来每个状态的超集的毒性和，然后可以$O(N_02^{N_0})$处理出来$F_i$，表示至少有$i$个$0$的毒性和，容斥即可
- 可以处理出来每个状态的子集的毒性和，然后可以$O(N_12^{N_1})$处理出来$G_i$，表示至多有$i$个$1$的毒性和，容斥即可
发现$\min(N_0,N_1,N_?)\le 6$，每次取最小的处理即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=(1<<20);
int L,Q,lim,num0,num1,num_;
int f[MAX],g[MAX],A[20],B[20],C[20],F[64];
char a[MAX],b[20];
int main()
{
scanf("%d%d%s",&L,&Q,a),lim=1<<L;
for(int i=0;i<lim;++i)
f[i]=g[i]=a[i]-'0';
for(int j=0;j<L;++j)
for(int i=0;i<lim;++i)
if(i&(1<<j)) f[i-(1<<j)]+=f[i];
for(int j=0;j<L;++j)
for(int i=0;i<lim;++i)
if(i&(1<<j)) g[i]+=g[i-(1<<j)];
for(int q=1,ans,T,T1;q<=Q;++q)
{
scanf("%s",b),num0=num1=num_=T=T1=ans=0;
for(int i=0;i<L;++i)
if(b[i]=='0') A[num0++]=i;
else if(b[i]=='1') B[num1++]=i,T+=1<<(L-i-1);
else if(b[i]=='?') C[num_++]=i,T1+=1<<(L-i-1);
if(num_<=6)
{
for(int i=0,x;i<(1<<num_);++i)
{
x=T;
for(int j=0;j<num_;++j)
if(i&(1<<j)) x+=1<<(L-C[j]-1);
ans+=a[x]-'0';
}
printf("%d\n",ans);
}
else if(num0<=6)
{
for(int i=0;i<=num0;++i)
F[i]=0;
for(int i=0,x,num;i<(1<<num0);++i)
{
x=T,num=0;
for(int j=0;j<num0;++j)
if(!(i&(1<<j))) x+=1<<(L-A[j]-1);
else ++num;
F[num]+=f[x];
}
for(int i=num0,tt=1;i>=0;--i)
ans+=tt*F[i],tt*=-1;
printf("%d\n",ans);
}
else if(num1<=6)
{
for(int i=0;i<=num1;++i)
F[i]=0;
for(int i=0,x,num;i<(1<<num1);++i)
{
x=T1,num=0;
for(int j=0;j<num1;++j)
if(!(i&(1<<j))) x+=1<<(L-B[j]-1);
else ++num;
F[num]+=g[x];
}
for(int i=0,tt=1;i<=num1;++i)
ans+=tt*F[i],tt*=-1;
printf("%d\n",ans);
}
}
return 0;
}
