AC. 梦想

frank_c1

集合卷积学习

发布于2017年03月11日 | 暂无评论 | 604阅读 | 高等数学

记得去年省选二试前我翻开vfk的集合幂级数论文,想要学习一波。

然而一年过去了,我发现我好像还没学。于是又是一年省选将至,我还是赶快把坑填了吧。

先定义两个主角

F(x) = \sum_{S \in 2 ^ U} {f_S x ^ S}

G(x) = \sum_{S \in 2 ^ U} {g_S x ^ S}

集合并卷积

定义F(x)G(x)的集合并卷积H(x)如下

H(x) = \sum_{S \in 2 ^ U} \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R = S] f_L g_R x ^ S}

我们关注

h_S = \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R = S] f_L g_R}

这里有一个相等的限制,一般这种限制我们不容易直接解决。回忆解决这类问题的方法,不妨考虑把相等改为子集的约束,再通过容斥求答案。

根据上面的思路,不妨设

\begin{aligned} \hat{h}_S = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \cup R \subseteq S] f_L g_R} \\ = & (\sum_{L \subseteq S} {f_L}) (\sum_{R \subseteq S} {g_R}) = \sum_{T \subseteq S} {h_T} \end{aligned}

这启发我们定义一种变换

\hat{h}_S = \sum_{T \subseteq S} {h_S}

同时由容斥原理得

h_S = \sum_{T \subseteq S} {(-1) ^ {|S|-|T|} \hat{h}_S}

此时我们发现

\hat{h}_S = \hat{f}_S \cdot \hat{g}_S

卷积转化为了点积,加速了计算。

我们知道了上面这种变换有一个优美的名字叫快速莫比乌斯变换(Fast Mobius Transform, FMT),可以在O(n 2 ^ n)的时间完成一次变换或者逆变换。这无疑比暴力计算的效率高多了。

集合对称差卷积

定义F(x)G(x)的集合对称差卷积H(x)如下

H(x) = \sum_{S \in 2 ^ U} \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R = S] f_L g_R x ^ S}

我们关注

h_S = \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R = S] f_L g_R}

首先考虑一个等式

\sum_{T \in 2 ^ U} {(-1) ^ {|S \cap T|}} = [S = \emptyset] 2 ^ n

代入原式化简

\begin{aligned} h_S = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {[L \oplus R \oplus S = \emptyset] f_L g_R} \\ = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {\frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap (L \oplus R \oplus S)|} f_L g_R}} \\ = & \sum_{L \in 2 ^ U} \sum_{R \in 2 ^ U} {\frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap L|} (-1) ^ {|T \cap R|} (-1) ^ {|T \cap S|} f_L g_R}} \\ = & \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} (\sum_{L \in 2 ^ U} {(-1) ^ {|T \cap L|}f_L}) (\sum_{R \in 2 ^ U} {(-1) ^ {|T \cap R|} g_R})}\end{aligned}

\hat{h}_S = (\sum_{L \in 2 ^ U} {(-1) ^ {|S \cap L|}f_L}) (\sum_{R \in 2 ^ U} {(-1) ^ {|S \cap R|} g_R})

h_S = \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} \hat{h}_T}

大概是一个比较套路的反演?和上面类似,我们发现这里面也有一些类似的形式,启发我们定义这样的变换

\hat{h}_S = \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} h_T}

和逆变换

h_S = \frac{1} {2 ^ n} \sum_{T \in 2 ^ U} {(-1) ^ {|T \cap S|} \hat{h}_T}

此时我们发现

\hat{h}_S = \hat{f}_S \cdot \hat{g}_S

卷积又转化为了点积,又加速了计算。

我们同样知道上面这种变换也有一个优美的名字叫快速沃尔什变换(Fast Walsh Transform, FWT),可以在O(n 2 ^ n)的时间完成一次变换或者逆变换。这无疑又比暴力计算的效率高多了。