一个有关FWT&FMT的东西

这篇文章在讲什么

　　相信大家都会FWT和FMT。

　　如果你不会，推荐你去看一下VFK的2015国家集训队论文。

　　设全集为\(U=\{1,2,\ldots,n\}\)，假设我们关心的\(f_S\)中的集合\(S\)是\(U\)的子集。

　　给你\(c_i,d_i\)，令
\[
b_i=(1+c_ix^{d_i})
\]

　　求
\[
g=\prod_{i}b_i
\]
　　其中两个集合幂级数的乘积为集合并卷积（or）/集合对称差卷积（xor）中的一种。

　　不妨设\(d_S\)互不相同（否则可以用DP/组合数什么的搞一下）。

　　令
\[
\begin{align}
a_S&=\sum_{d_i=S}c_i\\
f_S&=1+a_Sx^S
\end{align}
\]

暴力做法

　　对于每一个集合幂级数暴力做一遍FMT/FWT，然后直接乘在一起，再变换回去。

　　时间复杂度：\(O(n4^n)\)

　　这个做法太慢了，因为它没有用到本题的特殊条件。

集合或卷积

　　对于一个集合幂级数\(f\)，定义\(f\)的莫比乌斯变换为集合幂级数\(\hat f\)，其中
\[
\begin{align}
\hat f_S=\sum_{T\subseteq S}f_T
\end{align}
\]
　　反过来，定义\(\hat f\)的莫比乌斯反演为\(f\)，由容斥原理可以得到
\[
f_S=\sum_{T\subseteq S}{(-1)}^{|S|-|T|}\hat f_T
\]
　　相信大家都熟悉以上内容。

　　回到我们要求的那条式子：
\[
\begin{align}
\hat g_T&=\prod_S \hat{f_{S}}_T\\
&=\prod_S \sum_{K\subseteq T}f_{S,K}\\
&=\prod_{S\subseteq T}{(1+a_S)}
\end{align}
\]
　　是不是发现和普通的莫比乌斯变换很像？

　　把所有\(a_S\)加上\(1\)，把莫比乌斯变换的加法改成乘法，就可以得到\(\hat g_T\)了。

　　时间复杂度：\(O(n2^n)\)

集合对称差卷积

　　还是要用到那几条式子。
\[
\begin{align}
\hat g_T&=\prod_S\hat {f_S}_T\\
&=\prod_S\sum_{K}f_{S,K}{(-1)}^{|K\cap T|}\\
&=\prod_S(1+a_S{(-1)}^{|S\cap T|})
\end{align}
\]
　　这个和沃尔什变换也很像，但是\({(-1)}^{|S\cap T|}\)只乘在了\(a_S\)上面，所以不能把\(a_S\)加\(1\)后做变种沃尔什变换。

　　但是我们可以再维护一个\(\hat h_T=\prod_S(1-a_S{(-1)}^{|S\cap T|})\)，把沃尔什变换中的\(-\hat g_T\)全部换成\(\hat h_T\)，就可以做了。

　　时间复杂度：\(O(n2^n)\)

代码

　　~~先坑着~~

　　(http://uoj.ac/submission/236983)

巴特西

一个有关FWT&FMT的东西

这篇文章在讲什么

暴力做法

集合或卷积

集合对称差卷积

代码

最新文章

热门文章