快速沃尔什变换FWT

大概在做CC月赛的时候看到了这样一道题：https://www.codechef.com/OCT17/problems/XORTREEH
题意是要你做一个%330301441的类似FWT的东西。定义数组A，B，C。定义一个操作$Aoplus B=C$

$$C[i]=sum_usum_v A[u] B[v] | u,v在k进制下不进位的和为i\ 其中k=2,3,4,...,9,10$$
要你求一个 $P=overset{X个A}{overbrace{Aoplus Aoplus...oplus A}}$
当k=2时，这是一个异或规则的FWT。
接下来考虑k=2的情况。假设ABC长度为2的幂次，用 $A_i$表示最高位为i的一段A。
$$那么\ C_0=A_0oplus B_0+A_1oplus B_1\ C_1=A_0oplus B_1+A_1oplus B_0\ 换一种表示方法：\ (C_0,C_1)=(A_0oplus B_0+A_1oplus B_1,A_0oplus B_1+A_1oplus B_0)$$
然后就在这里卡住了。。

然后去网上搜FWT，又听某dalao讲了，大概知道了一些思路。
构造一个$trans(A)=(trans(A_0+A_1),trans(A_0-A_1))$，以及逆变换$trans'(A)=(trans'(frac{A_0+A_1}{2}),trans'(frac{A_0-A_1}{2}))$。
然后有

$$trans(C)=trans(A)times trans(B)$$
这里的 $Atimes B=C$代表 $C[i]=A[i]B[i]$。
$所以C=Aoplus B\=trans'(trans(C))\=trans'(trans(A)times trans(B))$
然后如果是多个相乘就是

$D=Aoplus B oplus C\=trans'(trans(A)times trans(B)times trans(C))$

这里的$trans$和$trans'$操作都可以在$O(nlogn)$的时间内完成，所以总复杂度为$O(nlogn)$。

然后考虑k更大的情况，根据刚才的方法，我们需要一个能够在较低复杂度内实现的$trans_k$和他的逆变换$trans_k'$。

进行一些枚举，可以构造$trans(A)=(trans(A_0+A_1+A_2),trans(A_0+wA_1+w^2A_2),trans(A_0+w^2A_1+w^4A_2))$。其中$w^3=1$。

这时发现这个模数很牛逼啊，他保证了我存在$w$使$w^k=1$。

然后推广一波，好像很棒啊！复杂度大概是$O(knlog_kn)$?

最后

以上就是迷路小刺猬为你收集整理的快速沃尔什变换FWT的全部内容，希望文章能够帮你解决快速沃尔什变换FWT所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。