• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

FMT/FWT

admin

11月 28, 2021

用处

处理一些位运算卷积,(O(n2^n))

[c_i=sum_{k oplus j=i} a_k imes b_j
]

大体思想

构造某种映射,使得能够 (O(nlog n)) 内得到变换,假设原数列为 ({a_n}),新数列就是 ({fwt[a]_i})

然后知道了 ({fwt[a]_i})({fwt[b]_i}),能 (O(n)) 得到 ({fwt[c]_i})

最后还能够 (O(nlog n))(fwt[c]_i) 变换为 (c_i)

其实和 FFT 很像,就是解析式到点值再到解析式。

构造方法

Or

构造 (fwt[a]_i=sum_{j|i=i} a_j),也就是对 (i) 的所有子集求和。

这个构造有性质如下:

[egin{align}
fwt[a]_i imes fwt[b]_i&=sum_{j|i=i} sum_{k|i=i} a_j imes b_k \
&=sum_{(j|k)|i=i} a_j imes b_k \
&=fwt[c]_i
end{align}
]

假设现在处理完了前 (w-1) 位的 (fwt[c]_i),考虑怎么加入第 (w) 位的贡献。如果一个数的第 (w) 位是 0 ,那么它的或卷积是不会变的,如果是 1,那么答案就要累加上最高位为 1 的卷积。然后逆变换也是类似的,只是符号反过来。

[fwt[a]_i=merge(fwt[a_0]_i,fwt[a_0]_i+fwt[a_1]_i)
]

(merge) 表拼接。

void Or(int n,ll *a,bool op){
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        a[j|k|l]=(a[j|k|l]+(op? -1:1)*a[j|k]+Mod)%Mod;
}

And

与卷积与或卷积类似,有

[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i)
]

void And(int n,ll *a,bool op){
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        a[j|k]=(a[j|k]+(op? -1:1)*a[j|k|l]+Mod)%Mod;
}

Xor

构造运算 (xotimes y=count(x&y) mod 2)

有性质

[(xotimes y) xor (xotimes z)=xotimes(y^z)
]

可以构造变换 (fwt[a]_i=sum_{iotimes j=0} a_j-sum_{iotimes j=1}a_j)

得到

[fwt[a]_i=merge(fwt[a_0]_i+fwt[a_1]_i,fwt[a_0]_i-fwt[a_1]_i)
]

逆变时要除以 2。

void Xor(int n,ll *a,ll op){
    ll x,y;
    for(int w=2,l=1;w<=n;w<<=1,l<<=1)
    for(int j=0;j<n;j+=w)
    for(int k=0;k<l;k++)
        x=(a[j|k]+a[j|k|l])%Mod*op%Mod,
        y=(a[j|k]-a[j|k|l]+Mod)%Mod*op%Mod,
        a[j|k]=x,a[j|k|l]=y;
}

发表评论

您的电子邮箱地址不会被公开。