参考：https://www.cnblogs.com/ivorysi/p/9144676.html
但是参考博客讲解太吓人了，我们换一种通俗易懂的方法讲。
首先肯定是能想到容斥和子集和的，但是很尴尬的是，裸容斥的复杂度是O(2^l)的显然过不去。
我们考虑l特别小，且字符只有三种，话句话讲至少有一个字符个数<=6。
那我们就试图分情况讨论，分成以0,1,?为目标特殊处理。
同时我们：
设数组f[0][i]表示讨论0时i的二进制1集合属于j的二进制1集合时sigma(w[j])
设数组f[1][i]表示讨论0时j的二进制1集合属于i的二进制1集合时sigma(w[j])
这两个数组都能够在O(2^l)求出，接下来利用他们来导出答案。
PS：令x为原数中0集合，y为原数中1集合，z为原数中?集合。eg：原数101?，x=0100，y=1010，z=0001。
?
最简单的情况，暴力枚举即可。
0
枚举x的子集i。
我们求f[0][i|y]的目的就是将?和0空出来，再将0慢慢填上1达到容斥的效果。
（容斥不太好用语言表述还请见谅，请读者自行举例感受容斥。）
显然我们只填1的时候求的是全集，后面我们就要将0填上1来减去我们将0视为1所带来的多于的解（以及加上我们多减的）。
所以当当前的数i有偶数个1时要加，反之减。
1
枚举y的子集i。
我们求f[1][i|z]的目的同理将1和?填上，再将1慢慢填上0达到容斥的效果。
（容斥不太好用语言表述还请见谅，请读者自行举例感受容斥。）
显然我们?和1全填的时候求的是全集，后面我们就要将1填上0来减去我们将1视为0所带来的多于的解（以及加上我们多减的）。
所以当当前的数i比其y相差k个1时，k为偶要加，反之减。
（总之只要有耐心且不像我这么傻就能做出来的啦！~）
#include<cmath> #include<queue> #include<cstdio> #include<cctype> #include<vector> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int L=1048576; int k,q,f[2][L],w[L],calc[L]; char s[L]; int main(){ scanf("%d%d",&k,&q); cin>>s; for(int i=0;i<(1<<k);i++)w[i]=f[0][i]=f[1][i]=s[i]-'0'; for(int i=0;i<(1<<k);i++)calc[i]=calc[i>>1]+(i&1); for(int i=1;i<(1<<k);i<<=1){ for(int j=0;j<(1<<k);j++){ if(j&i)f[1][j]+=f[1][j^i],f[0][j^i]+=f[0][j]; } } while(q--){ cin>>s; int x=0,y=0,z=0,ans=0; for(int i=0;i<k;i++){ if(s[i]=='0')x|=(1<<(k-i-1)); else if(s[i]=='1')y|=(1<<(k-i-1)); else z|=(1<<(k-i-1)); } if(calc[x]<=6){ for(int i=x;;i=(i-1)&x){ if(calc[i]&1)ans-=f[0][i|y]; else ans+=f[0][i|y]; if(!i)break; } }else if(calc[y]<=6){ for(int i=y;;i=(i-1)&y){ if(calc[i^y]&1)ans-=f[1][i|z]; else ans+=f[1][i|z]; if(!i)break; } }else{ for(int i=z;;i=(i-1)&z){ ans+=w[i|y]; if(!i)break; } } printf("%d ",ans); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++