还是逃不掉多项式啊

快速沃尔什变换

对于一个位运算的卷积，即形式为$c_i=\Sigma a_j b_k [i==g(j,k)]$的求和，一般最简单最暴力的做法是遍历求和。

对于一个映射$f$，有

$$A\rightarrow f(A)\\ B\rightarrow f(B)\\ f(C)=f(A)*f(B) \Leftrightarrow f(c_i)=f(a_i)*f(b_i)\\ f(C)\rightarrow C$$

即找到一种变换，使得能将卷积等效为点乘，并且确定这个变换的逆变换，就可以用这个方法实现卷积。

数组点乘的复杂度是线性的，而遍历一个数组也至少是线性的，这个过程的主要复杂度就在变换和逆变换中。如果能找到一个优化的方法求出映射$f$与逆映射$f^{-1}$，就可以对卷积进行优化。

or卷积

卷积$c_i=\Sigma a_j b_k [i==(j|k)]$，可以发现对$c_i$有共献的下标$j,k$一定是$c_i$在二进制下的子集。

记$f(a_i)$是$A$中下标$i$的子集之和，求$f(A)$就变成了子集枚举问题。同样，如果要求逆，对$f(a_i)$做子集容斥就能得到$a_i$。

如果暴力去枚举子集，那和$n^2$暴力没什么区别。考虑用位运算子集的性质进行加速。最典型想法的就是fft中的奇偶分治，这里也可以套用。

$A\rightarrow f(A)$的过程是一个典型的折半分治，用沃尔什变换处理or卷积的时间复杂度是$O(nlogn)$的。

代码实现:

//逆运算:op=-1
void FWT_or(ll *a,ll *f,int op=1){
    ffor(i,0,n-1)f[i]=a[i];
    for(int mid=1;mid<n;mid<<=1)
    for(int p=0;p<n;p+=(mid<<1))
    for(int k=0;k<mid;++k)
    f[mid+p+k]=(f[mid+p+k]+op*f[p+k]+P)%P;
}

and卷积

卷积$c_i=\Sigma a_j b_k [i==(j\&k)]$，可以发现对$c_i$有共献的下标$j,k$一定是$c_i$在二进制下的超集。

同样的思路，记$f(a_i)$是$A$中下标$i$的超集之和，求$f(A)$就变成了补集枚举问题，本质上也是一个子集枚举。用沃尔什变换处理and卷积的时间复杂度也是$O(nlogn)$的。这个和or卷积写法都差不多

代码实现:

void FWT_and(ll *a,ll *f,int op=1){
    ffor(i,0,n-1)f[i]=a[i];
    for(int mid=1;mid<n;mid<<=1)
    for(int p=0;p<n;p+=(mid<<1))
    for(int k=0;k<mid;++k)
    f[p+k]=(f[p+k]+op*f[mid+p+k]+P)%P;
}

xor卷积

卷积$c_i=\Sigma a_j b_k [i==(j\oplus k)]$。异或不能像与和或那样简单地用子集关系表示，需要挖掘其他的性质。

考虑异或整体后的结果，似乎看不出来什么规律。拆位来看，若$i,j,k$表示当前bit的状态，则有$(i\&j)\oplus(i\&k)=i\&(j\oplus k)$，即位运算的分配律。

将这个关系推广到一个整数，同样是成立的。记$i \circ j=popcount(i\&j)\equiv 1 (mod 2)$，即两者与后bit数的奇偶性。存在

$$(i\circ j)\oplus(i\circ k)=i\circ(j\oplus k)$$

记$f(a_i)$是$A$中与下标$i$异或和bit数为偶数减去异或和bit数为奇数的和，即

$$f(a_i)=\Sigma a_j[i\oplus j \equiv 0(mod 2)]-\Sigma a_j[i\oplus j \equiv 1(mod 2) ]$$

在这个映射中，$f(a_i)f(b_i)$相乘后，套用上述性质，发现$f(c_i)$符合性质。

这个东西更像fft了，也可以用蝴蝶操作来优化。逆运算也同fft。异或卷积的时间复杂度是$O(nlogn)$级别的。

代码实现:

void FWT_xor(ll *a,ll *f,int op=1){
    ffor(i,0,n-1)f[i]=a[i];
    for(int mid=1;mid<n;mid<<=1)
    for(int p=0;p<n;p+=(mid<<1))
    for(int k=0;k<mid;++k){
        ll a0=f[p+k],a1=f[mid+p+k];
        f[p+k]=(((a0+a1)*op)%P+P)%P;
        f[mid+p+k]=(((a0-a1)*op)%P+P)%P;
    }
}

xnor卷积

卷积$c_i=\Sigma a_j b_k [i==(j xnor k)]$。同或是异或的对偶运算，当两者相同时取1。

同或也具有类似上述的性质，可以使用相同的思路来做，代码也是差不多的。

代码实现:

void FWT_xnor(ll *a,ll *f,int op=1){
    ffor(i,0,n-1)f[i]=a[i];
    for(int mid=1;mid<n;mid<<=1)
    for(int p=0;p<n;p+=(mid<<1))
    for(int k=0;k<mid;++k){
        ll a0=f[p+k],a1=f[mid+p+k];
        f[p+k]=(((a0-a1)*op)%P+P)%P;
        f[mid+p+k]=(((a0+a1)*op)%P+P)%P;
    }
}

例题

暂时鸽了（