FWT

  void FWT(LL a[],int len,int typ){
      LL mo,rev;
      if (typ==1) mo=mo1,rev=rev1;else mo=mo2,rev=rev2;
      for (int d=1;d<len;d<<=1)
        for (int i=0;i<len;i+=d*2)
          for (int j=0;j<d;j++){
            LL x=a[i+j],y=a[i+j+d];
          a[i+j]=(x+y)%mo;
          a[i+j+d]=(x-y+mo)%mo;    
                //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;    
                //and:a[i+j]=x+y;    
                //or:a[i+j+d]=x+y;    
        }    
  }
  
  void UFWT(LL a[],int len,int typ){
      LL mo,rev;
      if (typ==1) mo=mo1,rev=rev1;else mo=mo2,rev=rev2;
      for (int d=1;d<len;d<<=1)
        for (int i=0;i<len;i+=d*2)
          for (int j=0;j<d;j++){
            LL x=a[i+j],y=a[i+j+d];
          a[i+j]=(x+y)*rev%mo;
          a[i+j+d]=((x-y)*rev%mo+mo)%mo;
                 //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;    
                //and:a[i+j]=x-y;    
                //or:a[i+j+d]=y-x;    
        }    
  }            

 ----------------------------------------------------------------------------------------------------------------------------------------

考虑以下问题

ck=sigma(ai*bj),k=i|j,i&j=0

也就是不相交集合并。

可以将该问题的转移条件改为k=i|j,popcount(i)+popcount(j)=popcount(k)

于是我们可以将FWT的元素用多项式代替。若a数组的第i位有ai的值，则a位置的初始多项式为ai*x^popcount(i)。

FWT结果中第i位上x^popcount(i)的系数即为第i位的答案