逻辑、集合运算上的卷积一览（FMT、FWT,……）

公式渲染修好了。

简介

对于逻辑(oplus)的卷积，而且你不能N方豹草

[A_k=sum_{ioplus j=k} B_iC_j\ ]

那么尝试构造变换(F_{oplus})和反演(F_{oplus}^{-1})使满足

[F_{oplus}(A)_k=F_{oplus}(B)_k F_{oplus}(C)_k\ A_k=F_{oplus}^{-1}(F_{oplus}(A))_k ]

用来加速运算。

或与卷积

或与卷积的变换

定义或、与卷积的变换分别为

[F_{vee}(A)_k=sum_{ivee k=k}A_i,F_{wedge}(A)_k=sum_{iwedge k=k}A_i ]

如下验证两种变换的可行性

[egin{aligned} &egin{aligned} F_{vee}(B)_k F_{vee}(C)_k &=sum_{ivee k=k}B(i)sum_{jvee k=k}C(j) \&=sum_{xvee k=k}sum_{ivee j=x}B(i) C(j) \&=sum_{xvee k=k}A(x) \&=F_{vee}(A)_k end{aligned} &egin{aligned} F_{wedge}(B)_k F_{wedge}(C)_k &=sum_{iwedge k=k}B(i)sum_{jwedge k=k}C(j) \&=sum_{xwedge k=k}sum_{iwedge j=x}B(i) C(j) \&=sum_{xwedge k=k}A(x) \&=F_{wedge}(A)_k end{aligned} end{aligned} ]

验证成功。

如何实现这两种变换？注意到如果将(n)位二进制数域映射到一个(n)维空间，则(F_{vee}(A)_i)相当于在空间内求高维前缀和，(F_{wedge}(A))则是求高维后缀和。

因此直接上高维前/后缀和就能做到(O(n2^n))的复杂度，这样的做法属于“快速莫比乌斯变换”。

void FMT_OR(int a[],int len) {
    int n=__builtin_ctz(len);
	for(int i=0; i<n; ++i)
    	for(int j=0; j<len; ++j) if((j>>i)&1)
        	a[j]+=a[j^(1<<i)];
}
void FMT_AND(int a[],int len) {
	int n=__builtin_ctz(len);
	for(int i=0; i<n; ++i)
    	for(int j=len-1; ~j; --j) if((j>>i)&1)
        	a[j^(1<<i)]+=a[j];
}

还有一种通用的方法：“快速沃尔什变换”，复杂度同上。

我们把问题划为n+1个阶段编号0到n，在第i个阶段中，把序列划为(frac{2^n}{2^i})个区间，并记(F_{oplus}(A)_{i,x})表示x所在区间中所有下标与x就二进制末i+1位满足特定规则的元素累和。

例如(F_{oplus}(A)_{0,x}=A_x)，而所求(F_{oplus}(A)_x=F_{oplus}(A)_{n,x})。

从阶段i转移到阶段i+1时，阶段i+1的一个区间内的答案显然由阶段i中位置对应的相邻两个区间内的答案转移而来，此时决策为二进制第i+2末位的取与不取，即从(F_{oplus}(A)_{i,l+x})和(F_{oplus}(A)_{i,l+2^i+x})转移到(F_{oplus}(A)_{i+1,l+x})和(F_{oplus}(A)_{i+1,l+2^i+x})，其中l是阶段i+1中的某个区间的左端点。这四个状态，设为状态A,B,C,D，状态B,D能够表示取到第i+2末位。(其实B的取是假的，因为B不存在在i+2位产生的贡献)。转移按照变换式针对这四个状态做就好了。

例如或卷积中，A,B的下标或上(2^{i+1})（取到i+2位）得到D的下标，而只有A的下标或上(0)（不取i+2位）得到C的下标；只有B的下标与上(2^{i+1})（取到i+2位）得到D的下标，A,B的下标与上(0)（不取i+2位）得到C的下标。实现如下

void FWT_OR(int a[],int len) {
    for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) a[m+i+j]+=a[i+j];
}
void FWT_AND(int a[],int len) {
	for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) a[i+j]+=a[m+i+j];
}

或与卷积的反演

前/后缀和的反演还能怎么求……

[F_{vee}^{-1}(A)_k=sum_{ivee k=k} (-1)^{|k|-|i|}F_{vee}(A)_k\ F_{wedge}^{-1}(A)_k=sum_{iwedge k=k} (-1)^{|i|-|k|}F_{wedge}(A)_k ]

其中(|i|)是将(i)的二进制上(1)的个数。

先来“快速莫比乌斯反演”做法，直接把变换逆过来做

void IFMT_OR(int a[],int len) {
    int n=__builtin_ctz(len);
	for(int i=0; i<n; ++i)
    	for(int j=len-1; ~j; --j) if((j>>i)&1)
        	a[j]-=a[j^(1<<i)];
}
void IFMT_AND(int a[],int len) {
	int n=__builtin_ctz(len);
	for(int i=0; i<n; ++i)
    	for(int j=0; j<len; ++j) if((j>>i)&1)
        	a[j^(1<<i)]-=a[j];
}

然后是“快速沃尔什反演”做法，步骤与变换类似，只是累和改为消除。

void IFWT_OR(int a[],int len) {
    for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) a[m+i+j]-=a[i+j];
}
void IFWT_AND(int a[],int len) {
	for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) a[i+j]-=a[m+i+j];
}

异或卷积

异或卷积的变换

定义异或卷积的变换为

[F_{veebar}(A)_k=sum_{i} (-1)^{|iwedge k|}A_i ]

这次不去验证，考虑直接推导【膜rockdu】，首先假定变换(F_{veebar}(A))与(A)线性相关，如下，

[F_{veebar}(A)_k=sum_{i} g(k,i)A_i ]

当然(g(,))是需要能支持反演的，因此(g(,)=0)之类的就不考虑了。那么

[egin{aligned} F_{veebar}(A)_k&=sum_{i}g(k,i)A_i=sum_{i}g(k,i)sum_{pveebar q=i}B_pC_q \&=sum_{i}sum_{j}g(k,iveebar j)B_iC_j \ F_{veebar}(B)_k F_{veebar}(C)_k &=sum_{i}g(k,i)B_isum_{j}g(k,j)C_j \&=sum_{i}sum_{j}g(k,i)g(k,j)B_iC_j \ g(k,iveebar j)&=g(k,i) g(k,j) end{aligned} ]

我们需要构造一个(g(,))。

注意(|iveebar j|=|i|+|j|pmod2)，以及((iveebar j)wedge k=(iwedge k)veebar (jwedge k))，那么

[|(iveebar j)wedge k|=|(iwedge k)veebar(iwedge k) |=|iwedge k|+|jwedge k|pmod2\ (-1)^{|(iveebar j)wedge k|}=(-1)^{|iwedge k|}(-1)^{|jwedge k|} ]

因此令(g(k,i)=(-1)^{|iwedge k|})就能得到一个合法变换

[F_{veebar}(A)_k=sum_{i}(-1)^{|iwedge k|}A_i ]

如何实现这种变换？高维前/后缀和似乎已经G了，使用快速沃尔什变换，相邻两个阶段转移，要讨论对下标与的二进制1的个数的影响，结果如下

[F_{veebar}(A)_{i+1,l+x}=F_{veebar}(A)_{i,l+x}+F_{veebar}(A)_{i,l+2^i+x}\ F_{veebar}(A)_{i+1,l+2^i+x}=F_{veebar}(A)_{i,l+x}-F_{veebar}(A)_{i,l+2^i+x} ]

那么变换就完成了

void FWT_XOR(int a[],int len) {
    for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) {
                int x=f[i+j], y=f[m+i+j];
                f[i+j]=x+y;
                f[m+i+j]=x-y;
            }
}

异或卷积的反演

反演时的扣除贡献的式子就是把累和的式子反解，调整后如下

[F_{veebar}^{-1}(A)_{0,x}=F_{veebar}(A)_{n-1,x}\ F_{veebar}^{-1}(A)_{i+1,l+x}=frac{F_{veebar}^{-1}(A)_{i,l+x}+F_{veebar}^{-1}(A)_{i,l+2^i+x}}2\ F_{veebar}^{-1}(A)_{i+1,l+2^i+x}=frac{F_{veebar}^{-1}(A)_{i,l+x}-F_{veebar}^{-1}(A)_{i,l+2^i+x}}2\ ]

实现如下

void FWT_XOR(int a[],int len) {
    for(int m=1; m<len; m<<=1)
        for(int i=0,s=m<<1; i<len; i+=s)
            for(int j=0; j<m; ++j) {
                int x=f[i+j], y=f[m+i+j];
                f[i+j]=(x+y)/2;
                f[m+i+j]=(x-y)/2;
            }
}

可以发现所有的/2是可以留到后头算的，即

void IFWT_XOR(int a[],int len) {
    FWT_XOR(a,len);
    for(int i=0; i<len; ++i) a[i]/=len;
}

混合卷积

子集卷积

要求卷积

[A_k=sum_{i}sum_{j} [ivee j=k][iwedge j=0] B_iC_j \=sum_{ivee k=k}sum_{jvee k=k} [|i|+|j|=|k|] B_iC_j ]

可以枚举补充一维集合大小，从小到大枚举集合大小，分别做一次或卷积，时间复杂度(O(n^22^n))。

其它卷积

还在补。