参考：

但是参考博客讲解太吓人了，我们换一种通俗易懂的方法讲。

首先肯定是能想到容斥和子集和的，但是很尴尬的是，裸容斥的复杂度是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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             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<
             
              >1]+(i&1); for(int i=1;i<(1<
              
               <<=1){ for(int j=0;j<(1<
               
                >s; int x=0,y=0,z=0,ans=0; for(int i=0;i
               
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++