然而我只会抄课件

定义及基本运算

集合幂级数和生成函数一样,也是形式幂级数的一种。

设 $F$ 是一个域,则称函数 $f:2^U \to F$ 为 $F$ 上的一个集合幂级数。对于每个 $S \in 2^U$ 记 $f_S$ 表示把 $S$ 代入函数 $f$ 后的函数值,并称 $f_S$ 为该集合幂级数第 $S$ 项的系数。注意这里的下标都是集合。

加减法比较好定义。容易得到集合幂级数形成了一个加法阿贝尔群,单位元是满足系数均为 $0$ 的集合幂级数。

为了看起来更顺眼 我们可以将集合幂级数表示为 $f=\sum_{x \subseteq 2^U} f_xx^S$。

接下来我们尝试定义集合幂级数的乘法,我们希望乘法有交换律,结合律,单位元最好是$\emptyset$。我们来考虑三种乘法:

集合并卷积

$$ h_s = \sum_{L \subseteq 2^U} \sum_{R \subseteq 2^U} [L \cup R=S]f_Lg_R $$

我们可以用快速莫比乌斯变换(FMT)来快速计算。

定义:对于一个集合幂级数 $f$ 我们定义 $f$ 的莫比乌斯变换为集合幂级数 $\hat f$ 满足

$$ \hat f_S = \sum_{T \subseteq S} f_T $$

我们也称 $f$ 是 $\hat f$ 的莫比乌斯反演。

如果我们直接对莫比乌斯变换后的函数按位相乘 可以观察一下式子:

$$ \begin{align*}\hat h_S &= \hat f_S \hat g_S\\&= \sum_{L \subseteq S}f_L\sum_{R \subseteq S} f_R\\&= \sum_{L \subseteq S}\sum_{R \subseteq S} f_L f_R\\&= \sum_{L \subseteq S}\sum_{R \subseteq S} [(L \cup R) \subseteq S]f_L f_R\\\end{align*} $$

所以这就是凑成了 $h$ 莫比乌斯变换后的形式。

莫比乌斯变换的实现实际上是要时间一个高维前缀和 可以用 FWT_OR 的做法实现(

这样就可以在时间复杂度为 $O(n2^n)$ 内求出集合并卷积了。

inline void OR(int f[]){
    for(int mid = 1;mid < N;mid <<= 1){
        for(int i = 0;i < N;i += (mid<<1)){
            FOR(j,0,mid-1){
                (f[i+mid+j] += f[i+j]) %= ha;
            }
        }
    }
}

inline void iOR(int f[]){
    for(int mid = N>>1;mid;mid >>= 1){
        for(int i = 0;i < N;i += (mid<<1)){
            FOR(j,0,mid-1){
                (f[i+mid+j] += ha-f[i+j]) %= ha;
            }
        }
    }
}

集合对称差卷积

首先定义集合的对称差运算

$$ A \otimes B = \{x|(x\in A)\text{xor}(x\in B)\} $$

所以对称差卷积的定义很容易得出:

$$ h_S=\sum_{L \in 2^U}\sum_{R \in 2^U}[L \otimes R=S]f_Lg_R $$

快速计算可以考虑使用快速沃尔什变换。

实际上这里就是 FWT_XOR 。我们接下来暂时丢掉集合 考虑更直观的异或卷积:

$$ f[i]\times g[j] \to h[i \text{ xor }j] $$

考虑定义运算 $x \oplus y=\text{popcount(x and y) mod 2}$,这个运算满足 $(i \oplus j) \text{ xor }(i \oplus k) = i \oplus(j \text{ xor }k)$

于是我们构造$f$ 的变换 $\hat f$

$$ \hat f_i = \sum_{i \oplus j=0}a_j-\sum_{i\oplus j=1}a_j $$

$$ \begin{align*}\hat h_i &= \sum_{i \oplus j=0}a_j\sum_{i\oplus k=0}b_k-\sum_{i\oplus j=1}a_j\sum_{i\oplus k=0}b_k-\sum_{i\oplus j=0}a_j\sum_{i\oplus k=1}b_k+\sum_{i\oplus j=1}a_j\sum_{i\oplus k=1}b_k\\&=\sum_{i\oplus (j \text{ xor } k)=0}a_jb_k-\sum_{i\oplus (j \text{ xor } k)=1}a_jb_k\\&= \hat f_i \hat g_i\end{align*} $$

也就是变换后直接按位相乘就能得到变换后的结果。

接下来是如何去快速实现这个变换 推荐去看一下这个博客

来源上面的博客 侵删

红色箭头表示负贡献,蓝色箭头表示正贡献。正变换就从下往上跑,负变换从上往下跑。复杂度 $O(n2^n)$

inline void XOR(int f[]){
    for(int mid = 1;mid < N;mid <<= 1){
        for(int i = 0;i < N;i += (mid<<1)){
            FOR(j,0,mid-1){
                int x = f[i+j],y = f[i+mid+j];
                f[i+j] = (x+y)%ha;f[i+mid+j] = (x+ha-y)%ha;
            }
        }
    }
}

inline void iXOR(int f[]){
    for(int mid = N>>1;mid;mid >>= 1){
        for(int i = 0;i < N;i += (mid<<1)){
            FOR(j,0,mid-1){
                int x = f[i+j],y = f[i+mid+j];
                f[i+j] = 1ll*(x+y)%ha*inv2%ha;f[i+mid+j] = 1ll*(x+ha-y)%ha*inv2%ha;
            }
        }
    }
}

集合幂级数就可以把集合抽象成二进制数一样做。。

子集卷积

比集合并卷积更加严格。定义两个集合幂级数的子集卷积为

$$ h_S = \sum_{L \in 2^U} \sum_{R \in 2^U} [L \cup R = S][L \cap R = \emptyset]f_Lg_R $$

快速做:

首先我们注意到 $[L \cup R=S][L \cap R = \emptyset] = [L \cup R = S][|L|+|R|=|S|]$。于是我们可以想到加一维大小限制来删去违法贡献。

论文上是这样写的:

一个 $F[[z]]$ 上的集合幂级数 $\sigma$ 为集合幂级数 $f$ 的集合占位幂级数定义为:

$$ \sigma = \sum_{S \in 2^U}f_Sz^{|S|}x^S+\sum_{S \in 2^U}\sum_{i = |S|+1}^{\infty} \sigma_{S,i}z^{i}x^{S} $$

实际上我们可以理解成:

$f[i][S]$ 表示集合 $S$ 大小为 $j$ 的答案。有转移 $f[i][S]\times f[j][T] \to f[i+j][S \cup T]$

然后我们只保留 $f[|S|][S]$ 的结果即可。

看起来就是一个二维 FFT。我们对于第一维暴力卷积 第二维做集合并卷积 时间复杂度 $O(n^22^n)$

比较高级的运算

求逆

定义集合幂级数 $g^{-1}$ 是 $g$ 的乘法逆元,当且仅当 $g\times g^{-1}=\epsilon$ 其中乘法定义为子集卷积, $\epsilon$ 是子集卷积单位元$x^{\emptyset}$ 那么我们只需要将其转化成集合占位幂级数 对每一位做多项式求逆即可。这里一般集合占位幂级数要用的部分都不会特别长,可以考虑 $O(n^2)$ 求逆:

设 $p$ 为一形式幂级数 $q$ 为 $p$ 的逆元,那么有

$$ \sum_{i=0}^n q_ip_{n-i} = [n=0]\\q_n=\begin{cases}\frac{1}{p_0},&n=0\\-\frac{1}{p_0}\sum_{i=0}^{n-1}q_ip_{n-i},&\text{otherwise}\end{cases} $$

$O(n^2)$ 递推即可。

exp & ln

我们做关于 $\exp,\ln$ 的东西的时候为了避免不收敛 强制 $x^{\emptyset}=0$

类比 EGF ,组成集合的个体的集合幂级数是 $f$ 集合的集合幂级数是 $g$ ,一般有

$$ e^{f} = g+1\\f = \ln(g+1) $$

这两个东西也可以通过先转化成集合占位幂级数 对每一位都求 $\exp,\ln$ 我们也需要了解一下 $O(n^2)$ 的做法:

ln

设 $g=\ln(f+1)$ 那么

$$ \begin{align} g' &= \frac{f'}{f+1}\\g'(f+1)&=f'\\g'+g'f&=f'\\g'_k+\sum_{i=0}^{k-1} g'_if_{k-i}&=f'_k\\(k+1)g_{k+1}+\sum_{i=0}^{k-1} (i+1)g_{i+1}f_{k-i}&=(k+1)f_{k+1}\\g_{k+1}&=f_{k+1} -\frac{1}{k+1}\sum_{i=0}^{k-1} (i+1)g_{i+1}f_{k-i} \end{align} $$

一定要多加注意是循环到 $n-1$

exp

设 $g=e^f$

$$ g'=f'e^f\\g'=f'g\\g'_k=\sum_{i=0}^k f'_ig_{k-i}\\(k+1)g_{k+1}=\sum_{i=0}^k (i+1)f_{i+1}g_{k-i}\\g_{k+1}=\frac{1}{k+1}\sum_{i=0}^k (i+1)f_{i+1}g_{k-i}\\ $$

开根

和上面的分析差不多,设 $g=\sqrt{f}$

$$ g^2 = f\\\sum_{i=0}^k g_ig_{k-i} = f_k\\2g_kg_0=f_k-\sum_{i=1}^{k-1}g_ig_{k-i}\\g_k=\frac{1}{2g_0}(f_k-\sum_{i=1}^{k-1}g_ig_{k-i})\\ $$

初始值 $b_0 = \sqrt a_0$

分治卷积

适用于解决:

$$ f_S=\sum_{T \subsetneq S} f_Tg_{S-T}\\f_S=\sum_{T \subsetneq S,T \neq \emptyset} f_Tf_{S-T}\\f_S=a_S+\sum_{T \subsetneq S}b_Tf_T\times c_{S-T}g_{S-T} $$

都可以使用分治卷积做到 $O(2^n n^2)$

其实暴力就可以。。转成集合占位幂级数之后枚举 $f[i][S]$ 中的 $i$ 然后暴力卷积+FMT 转移即可。好像就是州区划分那个题。(感觉毫无分治思想啊 (((

题目

「HAOI2015」按位或

我们把概率 $p$ 看成集合幂级数,如果将乘法定义成集合并卷积的话 恰好第 $k$ 轮结束的概率就是 $p^k-p^{k-1}$的第 $U$ 相、

于是答案就是

$$ \sum_{k \geq 1} (p^k-p^{k-1})k $$

设这个的集合幂级数为 $f$ 考虑做莫比乌斯变换

$$ \begin{align*}\hat f_S&=\sum_{k \geq 1} (\hat{p}^k_S-\hat p^{k-1}_S)k\\&= \sum_{k \geq 1}\hat{p}_S^{k-1}(\hat{p}_S-1)k\\&= (\hat{p}_S-1)\sum_{k \geq 0}\hat{p}_S^{k}(k+1)\\\text{令} T&=\sum_{k \geq 0}\hat{p}_S^{k}(k+1)\\&=\sum_{k \geq 0}k\hat{p}_S^{k}+\sum_{k \geq 0}\hat{p}_S^{k}\\&= \frac{1}{1-\hat{p}_S}+\sum_{k \geq 1} k\hat{p}_S^k\\&= \frac{1}{1-\hat{p}_S}+\sum_{k \geq 0} (k+1)\hat{p}_S^{k+1}\\&= \frac{1}{1-\hat{p}_S}+\hat{p}_S\sum_{k \geq 0} (k+1)\hat{p}_S^{k}\\&= \frac{1}{1-\hat{p}_S}+\hat{p}_ST\\\Rightarrow T&=\frac{1}{(1-\hat{p}_S)^2}\\\hat f_S &= \frac{\hat{p}_S-1}{(1-\hat{p}_S)^2}\\&= -\frac{1}{1-\hat p_S}\end{align*} $$

然后快速莫比乌斯反演回去就好了。时间复杂度 $O(n2^n)$

Topcoder SRM 518 Nim

就是求多少种方案异或值为 $0$

将每个数二进制位看成一个集合 构造形式幂级数

$$ (\sum_{t \in prime} x^{\text{set}(t)})^m $$

乘法定义为对称差卷积。也就是FWT 一下 做个快速幂 FWT 回去就好了。

「WC2018」州区划分

划分在一个集合 不满足条件只有可能是存在欧拉回路或者点个数为 $1$

我们设 $f_S$ 表示选择了 $S$ 集合内的所有点后答案,记 $sm_S$ 表示集合所有点的和带上 $p$ 次方。

预处理 $g_S$ 表示集合内的点划分在一个集合的贡献 如果不合法就是0.

$$ f_S = \frac{1}{sm_S}\sum_{T \subseteq S} f_Tg_{S-T} $$

暴力是 $3^n$ 的 不太能过。

考虑右边实际上是一个子集卷积 按照上面的办法搞一搞就 $O(n^22^n)$了。

连通生成子图计数

给一个 $n$ 个点的无向图 $G$ 求联通生成子图个数 $n \leq 20$

设 $f_S$ 表示 $G$ 由 $S$ 导出的子图的连通生成子图个数,$g_S$ 表示 $G$ 由 $S$ 导出的子图的生成子图个数。特别的 我们强制 $f_{\emptyset} = g_{\emptyset} = 0$

$g$ 比较好求:只需要处理出边数就可以。

所以 $e^f=1+g \Rightarrow f = \ln(g+1)$ 多项式全家桶即可。

Last modification:May 27th, 2020 at 08:01 pm
如果觉得我的文章对你有用,请随意赞赏