锐客网

  1. 首页 > it技术 > >

@总结|@总结 - 2@ 位运算卷积/子集卷积 —— FWT/FMT

目录

  • @0 - 参考资料@
  • @1 - 异或卷积概念及性质@
  • @2 - 快速沃尔什正变换（异或）@
  • @3 - 快速沃尔什逆变换（异或）@
  • @4 - 与卷积、或卷积@
  • @5 - 参考代码实现@
  • @6 - 关于 FMT（快速莫比乌斯变换）@
  • @7 - 例题与应用@
    • ＠dp 优化＠
    • @子集卷积@
    • @卷积逆运算@
@0 - 参考资料@ yyb 的讲解（FWT）
popoqqq 的讲解（FWT）
zjp 的讲解（FMT）
Dance-Of-Faith 的讲解（FMT）
@1 - 异或卷积概念及性质@ 现在已知两个 n 维的向量 \(A=(a_0,a_1,...,a_{n-1}),B=(b_0,b_1,...,b_{n-1})\)。定义异或卷积式：
\[A\oplus B=(\sum_{i\oplus j=0}a_i*b_j,\sum_{i\oplus j=1}a_i*b_j,\dots,\sum_{i\oplus j=n-1}a_i*b_j)\]
定义加法 \(A\pm B=(a_0\pm b_0,a_1\pm b_1,...,a_{n-1}\pm b_{n-1})\)。
定义乘积 \(A*B=(a_0*b_0,a_1*b_1,...,a_{n-1}*b_{n-1})\)。
定义\(A_0=(a_0,a_1,...a_{n/2-1}),A_1=(a_{n/2},a_{n/2+1},...,a_{n-1})\)，则有 \(A=(A_0,A_1)\)。可以把 \(A_0,A_1\) 理解为向量 \(A\) 的前半部分与后半部分，也可以理解为 \(A\) 中二进制最高位为 0 的部分与二进制最高位为 1 的部分。
异或卷积有着良好的递归性质：
\[A\oplus B=(A_0\oplus B_0+A_1\oplus B_1,A_1\oplus B_0+A_0\oplus B_1)\]
怎么理解呢？根据我刚刚说的 \(A_0,A_1\) 的定义，讨论最高位为 0 或 1 就可以得到如上的式子。
这些运算有以下几个性质。
（1）\(A\oplus B=B\oplus A,A+B=B+A\)（交换律）
（2）\(A\oplus B\oplus C=A\oplus (B\oplus C),A+B+C=A+(B+C)\)（结合律）
（3）\(A\oplus (B+C)=A\oplus B+A\oplus C\)（分配律）
证明可以根据定义，拆 \(\sum\) 得到。
@2 - 快速沃尔什正变换（异或）@ 回想我们的加法卷积 \(C_k=\sum_{i+j=k}a_i*b_j\)，可以用 FFT 高效解决。
我们根据 FFT 的优化思路，来得到异或卷积的高效算法 FWT。
在搞 FFT 的时候，我们是先把原多项式 \(A(x)\) 由系数表示转为点值表示，再直接逐个相乘，最后由点值表示转回成系数表示。
将系数表示的多项式抽象成一个向量 \(A=(a_0,a_1,...,a_{n-1})\)
将点值表示的多项式也抽象成一个向量 \(A'=(a'_0,a'_1,...,a'_{n-1})\)，其中\(a'_i=A(w_n^i)\)。
则 FFT 的优化思路就可以抽象出来：将原向量\(A\)转化为新向量\(A'\)，使原向量的卷积\(A\oplus B\)对应着新向量的乘积\(A'*B'\)，最后把乘积转化为卷积。
我们定义一个函数 \(FWT(A) = A'\)，一个定义域和值域都为向量的函数，使得 \(FWT(A\oplus B)=FWT(A)*FWT(B)\)。再定义它的反函数 \(IFWT(A') = A\)。
则我们的 FFT 相当于选用了一个特殊的 \(FWT\) 函数，可以让我们快速求解\(FWT(A),IFWT(A')\)。
对于异或卷积而言，我们构造性地选取 \(FWT\)。
定义异或卷积的 \(FWT\) 函数为：
\[FWT(A)=\begin{cases} (FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) & (n>0)\\ A & (n=0)\end{cases}\]
【敲黑板，划重点，这个必考】
我们来验证一下这玩意具有上面那个性质。
性质（1）：\(FWT(A+B)=FWT(A)+FWT(B)\)
证明：\(FWT(A+B)\) 中的每一项都是线性组合，故满足分配律。
性质（2）：\(FWT(A\oplus B)=FWT(A)*FWT(B)\)
证明：数学归纳法。【集中注意力！！！】
当 n = 1 时，显然成立。
假设对于 k <= n-1 结论成立，则：
\[\begin{aligned} FWT(A\oplus B)&=FWT((A_0\oplus B_0+A_1\oplus B_1,A_1\oplus B_0+A_0\oplus B_1))&\\ &=(FWT(A_0\oplus B_0+A_1\oplus B_1)+FWT(A_1\oplus B_0+A_0\oplus B_1),FWT(A_0\oplus B_0+A_1\oplus B_1)-FWT(A_1\oplus B_0+A_0\oplus B_1))&\\ &=(FWT(A_0\oplus B_0+A_1\oplus B_1+A_1\oplus B_0+A_0\oplus B_1),FWT(A_0\oplus B_0+A_1\oplus B_1-A_1\oplus B_0-A_0\oplus B_1))&\\ &=(FWT((A_0+A_1)\oplus (B_0+B_1)),FWT((A_0-A_1)\oplus (B_0-B_1))&\\ &=(FWT(A_0+A_1)*FWT(B_0+B_1),FWT(A_0-A_1)*FWT(B_0-B_1))&\\ &=(FWT(A_0+A_1),FWT(A_0-A_1))*(FWT(B_0+B_1),FWT(B_0-B_1))&\\ &=FWT(A)*FWT(B) \end{aligned}\]
稍微分析我们每个等号都用了哪些性质。
第一个：用了异或卷积本身的递归性。
第二个：用了 FWT 的定义。
第三个：用了性质 \(FWT(A+B)=FWT(A)+FWT(B)\)。
第四个：用了因式分解。
第五个：用了我们数学归纳法的归纳前提。
第六个：用了一个恒等变换（类因式分解），可以验证等式左右两边是相等的。
第七个：逆用了 FWT 的定义。
然后得证我们的结论。
……
只能说很壮观。当初想出来这玩意儿的人真的是不容易。
所以我选择直接背定义。
根据 FWT 的定义，我们可以进行迭代求解。时间复杂度与 FFT 相同，为O(nlog n)。
@3 - 快速沃尔什逆变换（异或）@ 好了，正变换搞定了，我们可以写 FWT 了……
稍等。好像还差些什么。
……
好的我们来看看逆变换怎么弄。
由定义可得：\(FWT(A)=(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))=A'\)。
因此有\(\begin{cases} A'_0=FWT(A_0)+FWT(A_1)&\\ A'_1=FWT(A_0)-FWT(A_1) \end{cases}\)
解一下这个二元方程组就可得：\(\begin{cases} FWT(A_0)=\frac{A'_0+A'_1}{2}&\\ FWT(A_1)=\frac{A'_0-A'_1}{2} \end{cases}\)
两边同时进行逆变换可以得到：\(\begin{cases} A_0=IFWT(\frac{A'_0+A'_1}{2})&\\ A_1=IFWT(\frac{A'_0-A'_1}{2}) \end{cases}\)
所以：\(IFWT(A')=A=(A_0,A_1)=(IFWT(\frac{A'_0+A'_1}{2}),IFWT(\frac{A'_0-A'_1}{2}))\)
简化一下，加上边界： \[IFWT(A)=\begin{cases} (IFWT(\frac{A'_0+A'_1}{2}),IFWT(\frac{A'_0-A'_1}{2})) & (n>0)\\ A & (n=0)\end{cases}\]
因此，我们也可以在 O(nlog n) 的时间复杂度内实现逆变换。
@4 - 与卷积、或卷积@ 要知道二进制的运算可不止异或。
定义与卷积，或卷积如下：
\[A|B=(\sum_{i|j=0}a_i*b_j,\sum_{i|j=1}a_i*b_j,\dots,\sum_{i|j=n-1}a_i*b_j)\\ A\&B=(\sum_{i\&j=0}a_i*b_j,\sum_{i\&j=1}a_i*b_j,\dots,\sum_{i\&j=n-1}a_i*b_j)\]
我们直接给出与卷积，或卷积的 FWT 与 IFWT 的表达式。
如果想要证明可以自行参照异或的证明思路进行证明 （或者直接背） 。
或卷积：
\[FWT(A)=\begin{cases} (FWT(A_0),FWT(A_1)+FWT(A_0)) & (n>0)\\ A & (n=0)\end{cases}\\ IFWT(A)=\begin{cases} (IFWT(A_0),IFWT(A_1)-IFWT(A_0)) & (n>0)\\ A & (n=0)\end{cases} \]
与卷积：
\[FWT(A)=\begin{cases} (FWT(A_0)+FWT(A_1),FWT(A_1)) & (n>0)\\ A & (n=0)\end{cases}\\ IFWT(A)=\begin{cases} (IFWT(A_0)-IFWT(A_1),IFWT(A_1)) & (n>0)\\ A & (n=0)\end{cases} \]
@5 - 参考代码实现@ 本代码为 洛谷P4717 的 AC 代码。
#include const int MOD = 998244353; const int INV = (998244353 + 1)/2; const int MAXN = (1<<17); void fwt_or(int *a, int n, int type) { for(int s=2; s<=n; s<<=1) { int t = (s>>1); for(int i=0; i>1); for(int i=0; i>1); for(int i=0; i

@6 - 关于 FMT（快速莫比乌斯变换）@ 感觉……其实也不是很有用的样子。
完全可以被 FWT 替代啊。（可能常数要小一点？）
FMT 用于解决这样一类卷积问题（子集并卷积）：
\[f(S) = \sum_{T1\bigcup T2 = S}g(T1)*h(T2)\]
\(S, T1, T2\) 都是集合，其中 \(T1,T2\subset S\)，f, g, h 是定义在集合上的一个权值。
FMT 仿照 FFT 的方法，将集合转换为另一种处理起来更为方便的形式。定义：
\[\hat f(S)=\sum_{T\subset S}f(T)\]
即 S 集合的所有子集权值之和。
依照这个定义，就有：
\[\hat f(S)=\sum_{T1\bigcup T2 \subset S}g(T1)*h(T2)\]
我们知道子集之间的并集还是子集，所以就有：
\[\hat f(S)=\sum_{T1,T2 \subset S}g(T1)*h(T2)\]
根据乘法分配律，可以得到：
\[\hat f(S)=(\sum_{T \subset S}g(T))*(\sum_{T \subset S}h(T))=\hat g(S)*\hat h(S)\]
然后我们的目的就达成了，我们把卷积转换成了乘积。
再考虑怎么进行逆变换。根据容斥原理，可以得到：
\[f(S)=\sum_{T\subset S}(-1)^{|S|-|T|}\hat f(T)\]
可以考虑 S 每一个子集对答案的贡献，是组合数代数和的形式，即 C(n,0) - C(n,1) + C(n,2) ... 。这是一个经典的容斥式子，只有当 n = 0 时它等于 1，所以这个逆变换是成立的。
考虑代码实现，一种暴力的想法是 3^n 枚举子集计算。
但是我们发现这个式子长得非常 dp，所以我们考虑用递推来解决这一问题。
定义 dp[i][s] 表示我们通过删去元素 1 ... i 中的一些，能得到的子集之和。
则通过对第 i 个元素的讨论，可以得到转移式 dp[i][s] = dp[i-1][s] + dp[i-1][s - {i}]。
然后第一维可以直接滚动数组。
逆变换的话，我们的 dp 转移式就变成了 dp[i][s] = dp[i-1][s] - dp[i-1][s - {i}]。因为每多一个元素，上面公式中 -1 的幂就要增加 1。
代码比较简短（type 为 1 时为正变换，type 为 -1 时为逆变换）：
void fmt(int A[], int n, int type) { for(int i=1; i

好了。为什么我说这个东西可以被 FWT 替代呢？因为如果把集合用相应的二进制数表示，我们所说的子集并卷积其实就是或卷积。包括我在网上看到的子集卷积，子集逆卷积都可以用或卷积来替代。因为其实我们并没有用到 FMT 独特的一些性质，只是使用 FMT 来将卷积转换为乘积，而这个我们 FWT 也可以干。
可能 FMT 的优势就在于代码稍微短一些，理解起来容易一些，更方便背代码。
@7 - 例题与应用@ ＠dp 优化＠
身为一个卷积怎么可以不用来优化 dp?
假如我们列出了 dp 转移式子，发现它具有异或卷积的特征，我们就可以使用 fwt 进行优化。
比如：hdu - 5909 Tree Cutting 这道题就非常的典型。
另外，我们 fwt 也可以像 fft 一样进行卷积快速幂，比如这一道例题：bzoj - 4589 Hard Nim。
@子集卷积@
有些情况下，可能题目在异或卷积的前提下会加上更多的限制：比如一个集合必须与另一个集合无交集（对应位运算即 i xor j = i+j），或者说一个集合必须是另外一个集合的子集（对应位运算即 i xor j = i-j）。
在这个时候，我们通常会去限定二进制表示下 1 的个数，从而达到题目给出的限制。
比如这道题：hdu - 6057 Kanade's convolution
@卷积逆运算@
当然有可能会让你作卷积除法。方法比较简单，fwt 作正变换过后直接相除即可。（为什么 fft 不可以这样做呢？因为 fft 得到的结果项数可能是无穷多的，而 fwt 得到的结果项数是完全已知的）。
如果是子集卷积作除法，先限制二进制 1 的个数，然后 fwt 正变换完过后，因为二进制 1 的个数不会很大，所以直接暴力求解即可。
有一道雅礼集训出现的题目：union
【@总结|@总结 - 2@ 位运算卷积/子集卷积 —— FWT/FMT】转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/10165222.html

    推荐阅读


    上一篇：在服务器端对sshd做白名单

    下一篇：【iOS】iOS11限权访问问题