快速沃尔什变换备忘录

这真的仅仅是一个备忘录,没什么自己的东西
包含一些莫比乌斯变换的东西
我一开始就到 picks 的博客上去学果然是个错误的决定,表示学完之后云里雾里
然后又找了几个博客,还是不太明白,果然是因为我太渣了
然后到学长的博客上去看了一下,真是好明白多了
既然别人有写得很仔细的文章了,我就懒得写了,可以到底下链接去看,我只会写一些我学习时遇到的一点问题

部分解释

设 $\hat A _ i$ 为 $A$ 的莫比乌斯变换 : $\hat A _ i = \sum_{j\subseteq i} A_j$
当 $i$ 表示二进制位时, $j\subseteq i$ 表示 $j$ 的二进制位包含于 $i$
设 $F_i=\sum_{j \cup k = i} A_j\cdot B_k$
于是
$$
\begin{eqnarray}
\hat A _ n * \hat B _ n &=& \sum _ {i\subseteq n} A_i \sum _ {j\subseteq n} B_j \\
&=& \sum_{(i|j)\subseteq n} A_i B_j \\
&=& \sum_{k\subseteq n} \sum _ {(i|j)=k} A_i\cdot B_j \\
&=& \sum_{k\subseteq n} F_k \\
&=& \hat F_n \\
\end{eqnarray}
$$
然后其他的就比较好理解了
膜膜学长

莫比乌斯变换

快速莫比乌斯变换 (FMT)

$$ \hat f_S=\sum_{x\subseteq S} f_x $$
可以将 $n$ 集合划分成左右两部分递归做,然后分别考虑某一边对另外一边的考虑,这个方法在 FWT 里也用到了

快速莫比乌斯反演(FMI)

$$ f_S = \sum_{x\subseteq n}(-1)^{|S|-|x|} \hat f_x $$
这个还比较重要的,因为经常要用 $\hat f$ 反演出 $f$ ,就需要用到这个

子集卷积

顺便讲一下子集卷积
$$ f_U = \sum_{S\cup T = U , S\cap T = \varnothing} g_S\times h_T $$
看上去就是一个或卷积,但是多出一个条件 $S\cap T = \varnothing$
看上去不好处理,但是可以将式子转化
$$ f_U = \sum_{S\cup T = U, |S|+|T|=|U|} g_S\times h_T $$
此时发现只要满足集合大小相加方面的限制就行了
考虑加一维,设 $f_{S,i}$ 为代表集合 $S$ ,大小为 $i$ 的集合幂级数,所以有
$$ f_{U, i} = \sum_{S\cup T = U, j+k=i} g_{S,j}\times h_{T,k}$$
$$ \hat f_{U, i} =\sum_{s\cup T = U, j + k = i} \hat g_{S, j}\times \hat h_{T, k} $$
于是做完 $FMT$ 后枚举集合($\mathcal{O(2^n)}$),枚举 $\hat f$ 的集合大小($\mathcal{O(n)}$),枚举 $\hat g$ 的集合大小($\mathcal{O(n)}$)可以算出 $f$ 的子集卷积
时间复杂度 $\mathcal{O(n^2 2^n)} $
例题第四题

例题

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注