好题。
题意
给你 \(0\sim 2^k-1\) 这 \(2^k\) 个数，第 \(i\) 个数的权值是 \(a_i\)。有 \(q\) 次询问，每次询问给出一个由 0,1,? 组成的字符串，你需要把 ? 替换成 0,1，替换后把该串视为一个二进制数 \(x\)，求所有可能的 \(x\) 的权值和。
\(k\le 20,q\le 10^6\)
分析
有一个非常显然的暴力就是爆搜所有 ? 填什么，时间复杂度 \(O(q2^{cnt_?})\)。
但是肯定过不去。
注意到 \(\min(cnt_0,cnt_1,cnt_?)\le \frac{n}{3}=6\)，启发我们思考能不能在 0 和 1 上搞事情。
假设 \(cnt_1\le 6\)，发现难点在于 1 这些位只能取 1 而不像 ? 可以任取，如果没有 1 那么直接高维前缀和就行。结合给的条件，考虑容斥，钦定某些 1 错填 0，其他 1 视为 ? 一样填，容斥系数即是 \((-1)^{错填成0的1数量}\)，时间复杂度 \(O(q2^{cnt_1})\)。
当 \(cnt_0\le 6\) 时，做法和 \(cnt_1\le 6\) 没啥太大的不一样，但是注意要做的变成了高维后缀和。
当 \(cnt_?\le 6\) 时套用朴素爆搜。
时间复杂度 \(O(q2^{\frac{n}{3}})\)。代码非常好写。
const int maxn=21,maxm=1<<20,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int k,Q,n;
int a[maxm];
char s[maxn];
int f[maxm],g[maxm];
vector<int>v0,v1,v2;
inline int dfs2(int step,int id){
if(step==(int)v2.size())return a[id];
return dfs2(step+1,id)+dfs2(step+1,id|(1<<v2[step]));
}
inline int dfs0(int step,int id,int fir){
if(step==(int)v0.size())return fir*g[id];
return dfs0(step+1,id,fir)+dfs0(step+1,id|(1<<v0[step]),-fir);
}
inline int dfs1(int step,int id,int fir){
if(step==(int)v1.size())return fir*f[id];
return dfs1(step+1,id,-fir)+dfs1(step+1,id|(1<<v1[step]),fir);
}
inline void solve_the_problem(){
k=rd(),Q=rd(),n=1<<k;
rep(i,0,n-1)scanf("%1d",&a[i]);
rep(i,0,n-1)f[i]=g[i]=a[i];
rep(i,1,k){
rep(S,0,n-1){
if((S>>(i-1))&1)f[S]+=f[S^(1<<(i-1))];
else g[S]+=g[S^(1<<(i-1))];
}
}
while(Q--){
scanf("%s",s+1);
v0.clear(),v1.clear(),v2.clear();
rep(i,1,k){
if(s[i]=='0')v0.pb(k-i);
if(s[i]=='1')v1.pb(k-i);
if(s[i]=='?')v2.pb(k-i);
}
if(v2.size()<=6){
int S=0;
rep(i,1,k)if(s[i]=='1')S|=(1<<(k-i));
write(dfs2(0,S));
}else if(v0.size()<=6){
int S=0;
rep(i,1,k)if(s[i]=='1')S|=(1<<(k-i));
write(dfs0(0,S,1));
}else{
int S=0;
rep(i,1,k)if(s[i]=='?')S|=(1<<(k-i));
write(dfs1(0,S,1));
}
}
}