总结一下有关子集变换的笔记。

快速莫比乌斯变换

子集与

考虑形式化的问题:对于两个序列,我们希望求

更一般的,我们想求的是

其中是集合。接下来的问题与过程形式都使用集合来展现。

考虑做一个高维后缀和的变换:

则可以得到

高维后缀和可以写成

for(int i=0;i<n;i++){
    for(int j=0;j<(1<<n);j++)
        if((j&(1<<i))==0)
            s[j]+=s[j+(1<<i)];
}

在求出了后,我们希望还原成,可以用容斥得到

但这样做未免麻烦。直接做高维后缀差分即可。

for(int i=0;i<n;i++){
    for(int j=0;j<(1<<n);j++)
        if((j&(1<<i))==0)
            s[j]-=s[j+(1<<i)];
}

子集或

我们考虑一个一般化的问题。对于序列,我们想求

同样的,我们这次做高维前缀和

则可以推出

于是使用高维前缀和与高维前缀差分即可。

扩域情况

如果每一维是一个向量?

相当于与运算;相当于后缀和操作。

分治多项式乘法

我们有两个多项式,我们想求。设

假定。则我们有

而我们知道

因此可以只算的乘法,递归下去。时间复杂度

快速沃尔什变换

异或卷积

考虑形式化的问题。对于,我们要求

由于异或具有结合律、交换律,对加法的分配律,则我们用多项式乘法表示上述过程。即

(可以理解为在合并系数和指数的时候,加法是异或运算)设

则使用分治多项式乘法可以得到

(可以理解为,)我们设

于是可以得到

这样时间复杂度就是

这就是异或卷积本质上在做的事情。事实上,与卷积和或卷积都可以使用分治多项式乘法去理解。

异或卷积与 FWT

FWT 和 IFWT 的递归过程为

异或卷积则是 FWT 后直接做乘法:

事实上,。因此非递归版本的 IFWT 也可以直接在最后除掉一个

异或 FWT 本质

FWT 的本质是把变成了

写成集合幂级数的形式就是

有一个小 Trick 就是,如果我们修改,那么等变换回去后,所有项都被增加一个常量(这个常量不一定等于我们修改的差量)。原因如上所述,的贡献永远是正的。

这个性质可以用来解一些要求的题,那么我们给随机一个值,变换回去后把所有项都减掉即可。

模板代码

子集卷积

我们考虑这样一个问题:求不相交的或卷积:

这个不好求。则我们设

则可以得到

我们设

则答案显然为。因为,所以当且仅当时有。于是

于是做一个前缀差分即可。

总结来说,我们将变成,然后暴力卷积计算,最后还原成对应的。设全集为,则复杂度为

在实现的时候有一个技巧,就是在暴力卷积的时候要稍微调整循环顺序,不要一列一列访问内存,不然常数极大。

代码

HDU 5823

首先显然色数是的,因为你每个点染不同颜色一定是成立的。

而显然每种颜色可以染一个独立集。设表示点集是否是一个独立集,表示点集能否使用种颜色染。则

但事实上不是必要条件,它不会影响最优解。因此这就是一个子集或卷积,需要做次,每次卷完要回来转成艾弗森括号运算值。总复杂度

代码

CF1034 E

可以使用上述子集卷积做法,复杂度,在这道题中是不能通过的。

且令

容易发现

所以可以子集前缀差分算出

而注意到当时,。因此,于是

算的时候开 LL 暴力右移即可。

代码

HDU 5330

这道题虽然名称上是状圧 DP,但在 DP 的过程中是按维度考虑,其实是在做一个高维前缀和的过程。这样就更容易理解它 DP 的含义了。

具体的 DP 方法可以见注释。

代码

AGC034 F

表示从变到的期望:

。注意到这是一个异或卷积的形式(),则这个等式可以被表示为

,不满足和式,因此表示为状态。

由于,而在上述异或卷积中每个都和所有的乘起来贡献了一次。因此

于是得到

我们想办法把所有消掉:

于是我们 FWT 之后计算,然后再转回来即可。因为最后的答案是强制,所以在做的时候可以直接乘上逆元。最后使用 FWT 本质的 Trick 即可。

时间复杂度

代码