over 2 years ago

前言

看了好久集合的莫比乌斯变换,终于搞懂了集合并卷积,见一下自己的理解吧。。。

分析

首先,我们对于一个函数,定义其莫比乌斯变换为:

根据容斥原理,定义莫比乌斯反演为:

好吧这两个操作就是对称的(感觉我说了几句废话。。。)
其实如果你把前者看成点值表示,后者看成插值,会更好理解。
我们再来看看集合并卷积,定义为:

(其实就是把卷积中间加了个并的条件。。。依旧是废话)
我们分别对左右进行莫比乌斯变换,得到:

(为啥两边可以同时变换呢,因为点值表示后两边还是等价的啊)
(为啥集合并可以去掉呢,因为根据定义方程左边已经枚举了右边的所有的可能了)
到了这里是不是很excited呢?我们把卷积化成了类似FFT的点值乘法,然后就可以嘿嘿嘿了。
那么我们现在的问题就是怎么把函数在系数表示和点值表示之间快速变换呢?直接暴力是显然是不兹瓷的,我们可以做到
具体怎么搞,有两种方法,第一种是直接裸上分治乘法,第二种是稍微巧妙一点的递推,下面给出代码,具体为什么是这样,可以手推一下几个小数据,发现其实就是把集合给变相的分类。

//+1,-1分别表示系数>点值,点值>系数
template<class T>
inline void transform(T *A, int f) {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < (1<<n); ++j)
            if(j&(1<<i))
                A[j] += f*A[j^(1<<i)];
}

有了这些东西后,我们看看原题目,其实就是给定一个函数,求出函数

(注意这里的乘法是集合并卷积。。。)
我们把两遍同时莫比乌斯变换,得到:

是不是我们就得到了每一位的值啊,然后我们就可以莫比乌斯反演回去得到了,嘿嘿嘿我们就做完了。
bzoj4036.cpp

← bzoj2669:[cqoi2012]局部极小值 bzoj4037:[HAOI2015]Str →
 
comments powered by Disqus