初学FWT(快速沃尔什变换) 一点心得

FWT能解决什么

有的时候我们会遇到要求一类卷积，如下：

Ci=∑j⊕k=iAj∗Bk\large C_i=\sum_{j⊕k=i}A_j*B_kCi=j⊕k=i∑Aj∗Bk此处乘号为普通乘法，⊕⊕⊕表示一种位运算，如与 and(&)、and(\&)、and(&)、或 or(∣)、or(|)、or(∣)、异或 xor(xor(xor(^)))

LaTeX\Large\LaTeXLATEX打不了 ^ 啊…qwq

FWT思想

首先因为是位运算，所以需要按位分解。又因为是卷积的形式，联想到FFTFFTFFT中利用了一种分治优化降低时间复杂度，所以我们首先把多项式拓展到222的次幂长度，方便按位分治
FWTFWTFWT的思想就是利用一种向量变换来简化运算，首先我们定义向量VVV(此处可理解为数组或多项式)的正变换为FWT[V]FWT[V]FWT[V]，逆变换为FWT−1[V]FWT^{-1}[V]FWT−1[V]
- 先拿and(&)and(\&)and(&)的情况举例，根据位运算常识有
  
  (i&k) & (j&k)=(i&j) & k(i\&k)~\&~(j\&k)=(i\&j)~\&~k(i&k) & (j&k)=(i&j) & k
- 所以构造FWT[V]i=∑(j&i)=iVjFWT[V]_i=\sum_{(j\&i)=i}V_jFWT[V]i=∑(j&i)=iVj
  
  则有 FWT[C]i=FWT[A]i∗FWT[B]iFWT[C]_i=FWT[A]_i*FWT[B]_iFWT[C]i=FWT[A]i∗FWT[B]i
- 那么我们只需要求出FWT[A],FWT[B]FWT[A],FWT[B]FWT[A],FWT[B]，就能得到FWT[C]FWT[C]FWT[C]，然后通过逆变换求出CCC

变换与逆变换具体实现

像FFT一样，分治求FWT[V]FWT[V]FWT[V]。拿andandand运算举例
将一个长度为lenlenlen区间二分，那么左边和右边分别是最高位为0/10/10/1的数，此时递归处理左右两边。相当于先不考虑最高位，递归处理左右两边长度为len/2len/2len/2的答案
要想将两个区间合并，由于是andandand运算，两个数的与运算只会变小，那么只会是右边的区间对左边造成贡献
记左边处理出来的答案为XiX_iXi，右边处理出来的答案为YiY_iYi,合并后的答案为AnsiAns_iAnsi，XXX与YYY的实际含义为{Xi=∑i&j=i,j在左边VjYi=∑i&j=i,j在右边Vj\Large \left\{
\begin{aligned}
X_i=&\sum_{i\&j=i,j在左边}V_j\\
Y_i=&\sum_{i\&j=i,j在右边}V_j\\
\end{aligned}
\right.⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧Xi=Yi=i&j=i,j在左边∑Vji&j=i,j在右边∑Vj
显然有{Ansi=Xi+YiAnsi+len/2=Yi\Large \left\{
\begin{aligned}
&Ans_i=X_i+Y_i\\
&Ans_{i+len/2}=Y_i\\
\end{aligned}
\right.⎩⎪⎨⎪⎧Ansi=Xi+YiAnsi+len/2=Yi
求逆变换FWT[V]−1FWT[V]^{-1}FWT[V]−1时有{Xi=Ansi−Ansi+len/2Yi=Ansi+len/2\Large \left\{
\begin{aligned}
&X_i=Ans_i-Ans_{i+len/2}\\
&Y_i=Ans_{i+len/2}\\
\end{aligned}
\right.⎩⎪⎨⎪⎧Xi=Ansi−Ansi+len/2Yi=Ansi+len/2
于是我们就解决了与运算的问题，或运算可类比

异或卷积

异或(xor)(xor)(xor)与其他两个有点不一样(毕竟LaTeX\Large\LaTeXLATEX写不出来)，需要多想一想
异或卷积基于以下原理
- 定义iii和jjj之间的奇偶性为(i&j)(i\&j)(i&j)中为1的位数的奇偶性，若为偶数则奇偶性是0，若为奇数则奇偶性是1。记作d(i,j)d(i,j)d(i,j)
- 令FWT[V]i=∑d(i,j)=0Vj−∑d(i,j)=1Vj\large FWT[V]_i=\sum_{d(i,j)=0}V_j-\sum_{d(i,j)=1}V_jFWT[V]i=∑d(i,j)=0Vj−∑d(i,j)=1Vj
  
  就有了FWT[C]i=FWT[A]i∗FWT[B]i\large FWT[C]_i=FWT[A]_i*FWT[B]_iFWT[C]i=FWT[A]i∗FWT[B]i
  - 证明为d(i,k) xor d(j,k)=d(i xor j,k)d(i,k)~xor~d(j,k)=d(i~xor~j,k)d(i,k) xor d(j,k)=d(i xor j,k)
    - 将(i&k),(j&k)(i\&k),(j\&k)(i&k),(j&k)同时减去它们的相与的值(i&k)&(j&k)(i\&k)\&(j\&k)(i&k)&(j&k),它们的相对奇偶性(可以理解吧)不变，减去后(i&k),(j&k)(i\&k),(j\&k)(i&k),(j&k)在二进制下没有同时为111的位，所以异或可以直接相加
    - 所以当d(i,k)=d(j,k)d(i,k)=d(j,k)d(i,k)=d(j,k),同时减去后奇偶性还是相等，那么(i xor j)&k(i~xor~j)\&k(i xor j)&k的奇偶性=两个相等的奇偶性加起来=0=d(i,k) xor d(j,k)d(i,k)~xor~d(j,k)d(i,k) xor d(j,k)
    - 所以当d(i,k)!=d(j,k)d(i,k)!=d(j,k)d(i,k)!=d(j,k),同时减去后奇偶性还是不等，那么(i xor j)&k(i~xor~j)\&k(i xor j)&k的奇偶性=两个不等的奇偶性加起来=1=d(i,k) xor d(j,k)d(i,k)~xor~d(j,k)d(i,k) xor d(j,k)
  - 证毕(看懵逼的写两个二进制数来看看，很好理解的)
- 看看怎么分治，此处XXX与YYY的实际含义为{Xi=∑d(i,j)=0,j在左边Vj−∑d(i,j)=1,j在左边VjYi=∑d(i,j)=0,j在右边Vj−∑d(i,j)=1,j在右边Vj\Large \left\{
  \begin{aligned}
  X_i=&\sum_{d(i,j)=0,j在左边}V_j-\sum_{d(i,j)=1,j在左边}V_j\\
  Y_i=&\sum_{d(i,j)=0,j在右边}V_j-\sum_{d(i,j)=1,j在右边}V_j\\
  \end{aligned}
  \right.⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧Xi=Yi=d(i,j)=0,j在左边∑Vj−d(i,j)=1,j在左边∑Vjd(i,j)=0,j在右边∑Vj−d(i,j)=1,j在右边∑Vj
- 有{Ansi=Xi+Yi.................(1)Ansi+len/2=Xi−Yi.........(2)\Large \left\{
  \begin{aligned}
  &Ans_i=X_i+Y_i.................(1)\\
  &Ans_{i+len/2}=X_i-Y_i.........(2)\\
  \end{aligned}
  \right.⎩⎪⎨⎪⎧Ansi=Xi+Yi.................(1)Ansi+len/2=Xi−Yi.........(2)
- 怎么想呢，分类讨论吧。由于：
  - (1)(1)(1)对于左边区间的iii，根据X,YX,YX,Y的定义，显然满足
  - (2)(2)(2)而对于右边区间的iii
    - 当jjj在左边区间，j and ij~and~ij and i的值一定和j and (i−len/2)j~and~(i-len/2)j and (i−len/2)的值相等。所以加上XiX_iXi
    - 当jjj在右边区间，j and ij~and~ij and i的值一定和j and (i−len/2)j~and~(i-len/2)j and (i−len/2)的值相反。所以减去YiY_iYi
- 逆变换可自行推导(或看下方代码)

Luogu板题链接：P4717 【模板】快速沃尔什变换

写法跟FFT，NTT一模一样，还要更简(hao)单(bei)

AC code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 1<<17;

const int mod = 998244353;

const int inv2 = 499122177;

int n, a[MAXN], b[MAXN];

int a1[MAXN], a2[MAXN];

inline void FWT_or(int arr[], const int& len, const int& flg)

{

	register int x, y;

	for(register int i = 2; i <= len; i<<=1)

		for(register int j = 0; j < len; j += i)

			for(register int k = j; k < j + i/2; ++k)

			{

				x = arr[k], y = arr[k + i/2];

				if(~flg) arr[k + i/2] = (x + y) % mod;

				else arr[k + i/2] = (y - x + mod) % mod;

			}

}

inline void FWT_and(int arr[], const int& len, const int& flg)

{

	register int x, y;

	for(register int i = 2; i <= len; i<<=1)

		for(register int j = 0; j < len; j += i)

			for(register int k = j; k < j + i/2; ++k)

			{

				x = arr[k], y = arr[k + i/2];

				if(~flg) arr[k] = (x + y) % mod;

				else arr[k] = (x - y + mod) % mod;

			}

}

inline void FWT_xor(int arr[], const int& len, const int& flg)

{

	register int x, y;

	for(register int i = 2; i <= len; i<<=1)

		for(register int j = 0; j < len; j += i)

			for(register int k = j; k < j + i/2; ++k)

			{

				x = arr[k], y = arr[k + i/2];

				if(~flg) arr[k] = (x + y) % mod, arr[k + i/2] = (x - y + mod) % mod;

				else arr[k] = (LL)(x + y) * inv2 % mod, arr[k + i/2] = (LL)(x - y + mod) * inv2 % mod;

			}

}

inline void solve_or(const int& len)

{

	memcpy(a1, a, sizeof a);

	memcpy(a2, b, sizeof b);

	FWT_or(a1, len, 1);

	FWT_or(a2, len, 1);

	for(int i = 0; i < len; ++i)

		a2[i] = (LL)a1[i] * a2[i] % mod;

	FWT_or(a2, len, -1);

	for(int i = 0; i < len; ++i)

		printf("%d%c", a2[i], i == len-1 ? '\n' : ' ');

}

inline void solve_and(const int& len)

{

	memcpy(a1, a, sizeof a);

	memcpy(a2, b, sizeof b);

	FWT_and(a1, len, 1);

	FWT_and(a2, len, 1);

	for(int i = 0; i < len; ++i)

		a2[i] = (LL)a1[i] * a2[i] % mod;

	FWT_and(a2, len, -1);

	for(int i = 0; i < len; ++i)

		printf("%d%c", a2[i], i == len-1 ? '\n' : ' ');

}

inline void solve_xor(const int& len)

{

	memcpy(a1, a, sizeof a);

	memcpy(a2, b, sizeof b);

	FWT_xor(a1, len, 1);

	FWT_xor(a2, len, 1);

	for(int i = 0; i < len; ++i)

		a2[i] = (LL)a1[i] * a2[i] % mod;

	FWT_xor(a2, len, -1);

	for(int i = 0; i < len; ++i)

		printf("%d%c", a2[i], i == len-1 ? '\n' : ' ');

}

int main ()

{

	scanf("%d", &n); n = 1<<n;

	for(int i = 0; i < n; ++i) scanf("%d", &a[i]);

	for(int i = 0; i < n; ++i) scanf("%d", &b[i]);

	solve_or(n);

	solve_and(n);

	solve_xor(n);

}

巴特西

初学FWT(快速沃尔什变换) 一点心得

FWT能解决什么

FWT思想

变换与逆变换具体实现

异或卷积

Luogu板题链接：P4717 【模板】快速沃尔什变换

AC code

最新文章

热门文章