集合幂级数学习笔记

Author： RainAir
发布时间：May 12, 2020
1616views
No comments
1135 words
Categories：学习笔记

~~然而我只会抄课件~~

定义及基本运算

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

设 $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{aligned}\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{aligned} $$

所以这就是凑成了 $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{aligned}\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{aligned} $$

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

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

来源上面的博客侵删

红色箭头表示负贡献，蓝色箭头表示正贡献。正变换就从下往上跑，负变换从上往下跑。复杂度 $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{aligned} 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{aligned} $$

一定要多加注意是循环到 $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{aligned}\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{aligned} $$

然后快速莫比乌斯反演回去就好了。时间复杂度 $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：August 26th, 2020 at 08:55 am

如果觉得我的文章对你有用，请随意赞赏

集合幂级数学习笔记

RainAir • 2020 年 05 月 12 日

~~然而我只会抄课件~~

定义及基本运算

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

加减法比较好定义。容易得到集合幂级数形成了一个加法阿贝尔群，单位元是满足系数均为 $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$ 的莫比乌斯反演。

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

所以这就是凑成了 $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 $$

则

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

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

来源上面的博客侵删

红色箭头表示负贡献，蓝色箭头表示正贡献。正变换就从下往上跑，负变换从上往下跑。复杂度 $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)$

比较高级的运算

求逆

设 $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)$ 那么

一定要多加注意是循环到 $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)$

题目

「HAOI2015」按位或

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

于是答案就是

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

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

然后快速莫比乌斯反演回去就好了。时间复杂度 $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)$ 多项式全家桶即可。

定义及基本运算

集合并卷积

集合对称差卷积

子集卷积

比较高级的运算

求逆

exp & ln

ln

exp

开根

分治卷积

题目

「HAOI2015」按位或

Topcoder SRM 518 Nim

「WC2018」州区划分

连通生成子图计数