FWT

发表于 分类于

$\mbox{FWT}$ 知识点总结

FWT及FMT

先来看看FMT

我们记得，$\mbox{FFT}$做的是这样的卷积：$\sum_{i+j=k}A_iB_j=C_k$

但如果我们把符号换一下呢？

比如说或/与卷积：$\sum_{i|j=k}A_iB_j=C_k,\sum_{i&j=k}A_iB_j=C_k$

还是像fft的思路，考虑一个数组，有个变换，使得数组变换后能实现对应位置相乘。

即：$FMT(A)[x]\cdot FMT(B)[x]=FMT(C)[x]$.

当是或卷积时，$FMT(A)[x]=\sum_{i|x}A_i$.

因为：$(\sum_{i|x}A_i)(\sum_{j|x}B_j)=\sum_{i|x,j|x}A_iB_j=\sum_{k|x}(\sum_{i|j=k}A_iB_j)=\sum_{k|x}C_k$

那如何快速求 $FMT(A)$ 及其逆变换呢？

与卷积与或卷积类似：$FMT(A)[x]=\sum_{x|i}A_i$

考虑基于枚举二进制位的分治，假设第 $i$ 位的二进制已经处理完了，然后看加上第 $i+1$ 位后答案应该是怎么样的：如果这一位是 0，那么不变，否则因为是枚举子集，加上 $i+1$ 位不取的结果即可。

那么逆变换就是把正变换的贡献减去即可。

1
2
3
4
5
6
7
8
//或卷积模板,opt=1时为正变换，-1时为逆变换
void FMT(int * a, int n, int opt)
{
    for(int i=1;i<n;i<<=1)
        for(int p=i<<1,j=0;j<n;j+=p)
            for(int k=0;k<i;++k)
                A[i + j + k]+=opt*A[j + k];
}

或卷积的正变换其实就是高维前缀和（子集和），逆变换就是子集反演。

与卷积和或卷积类似了。

时间复杂度$O(n\log n)$

再来看看FWT

定义 $k$ 进制不进位加法：$a\bigoplus b=(a+b) % k$，减法类似。

FWT实际上就是求：$C_k=\sum_{i\bigoplus j=k}A_iB_j$

2进制FWT

此时不进位加法即为异或。以下 $n$ 满足 $n=2^x$

还是像fft的思路，考虑一个数组竖着排成一列变成一个 $n \times 1$ 的矩阵，然后有个变换，使得数组变换后能实现对应位置相乘。这个变换的实现就是令数组左乘一个 $n*n$ 的矩阵（可以回去看看fft的过程）。假设这个矩阵是 $T$，第 $i$ 行第 $j$ 列的数是 $T_{i,j}$

然后我们令$FWT(A)=TA$

因为要满足对应位置相乘，这里就是$FWT(A)[x]\cdot FWT(B)[x]=FWT(C)[x]$

由于$FWT(A)[x]=\sum_{i=0}^nT_{x,i}A_i$

代入上式得：$\sum_{i=0}^{n-1}T_{x,i}A_i\sum_{j=0}^{n-1}T_{x,j}B_j=\sum_{k=0}^{n-1}T_{x,k}C_k$

同时因为 $C_k=\sum_{i\bigoplus j=k}A_iB_j$

代入得：

$$\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}T_{x,i}T_{x,j}A_iB_j=\sum_{k=0}^{n-1}\sum_{i\bigoplus j=k}T_{x,k}A_iB_j$$

因此满足 $T_{x,i}T_{x,j}=T_{x,i\bigoplus j}=T_{x,(i+j)\bmod 2}$ 即可。

因为 $T_{x,i}$ 满足上述性质，把 $i$ 写成二进制形式：$i=\overline{i_0i_1\dots i_m}(2)$

因此 $T_{x,i}$ 可以等于 $\Pi {j=0}^m T{x_j,i_j}$

同时还需要快速算出 $FWT(A)$:

不妨设 $i$ 在二进制中最高位为 $i_1$，舍去最高位后为 $i_0$.

考虑分治：

$$FWT(A)n[i]\=\sum{k=0}^{n-1}T_{i,k}A_k\=T_{i_1,0}\sum_{k=0}^{n/2-1}T_{i_0,k_0}A_{k}+T_{i_1,1}\sum_{k=n/2}^{n-1}T_{i_0,k_0}A_k\=T_{i_1,0}FWT(A_0){\frac{n}{2}}[i]+T{i_1,1}FWT(A_1)_{\frac{n}{2}}[i]$$

其中 $A_0$ 为 $A$ 的前 $n/2$ 位，$A_1$ 为后 $n/2$ 位。

因此只要能找到合适的 $T_{x,i}$，就能实现了。

只需考虑 $0\le x,i < 2$ 的情况即可。

满足：

$$T_{0,0}\times T_{0,0}=T_{0,0}\T_{0,0}\times T_{0,1}=T_{0,1}\T_{0,1}\times T_{0,1}=T_{0,0}\T_{1,0}\times T_{1,0}=T_{1,0}\T_{1,0}\times T_{1,1}=T_{1,1}\T_{1,1}\times T_{1,1}=T_{1,0}\$$

考虑写成矩阵形式，构造可得：

$$\begin{bmatrix} T_{0,0}&T_{0,1}\ T_{1,0}&T_{1,1}\end{bmatrix}=\begin{bmatrix}1&1\1&-1\end{bmatrix}=\begin{bmatrix}\frac{1}{2}&\frac{1}{2}\\frac{1}{2}&-\frac{1}{2}\end{bmatrix}^{-1}$$

带进程序里即可。

一个2进制FWT的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
void FWT(ll *a,int n,int opt)
{
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++)
			{
				ll x = a[j+k],y = a[i+j+k];
				a[j+k] = x+y; a[i+j+k] = x-y+mod;
				if(a[j+k] >= mod) a[j+k] -= mod;
				if(a[i+j+k] >= mod) a[i+j+k] -= mod;
				if(t == -1) a[j+k] = (a[j+k]*inv2)%mod,a[i+j+k] = (a[i+j+k]*inv2)%mod;
			}
}

2进制 $\mbox{FWT}$ 的正变换实际上就是 $FWT[i]=\sum_{j}A_j(-1)^{|i&j|}$.

k进制FWT

以下 $n$ 满足 $n=k^x$

前面同理，但还是要满足 $T_{x,i}T_{x,j}=T_{x,i\bigoplus j}=T_{x,(i+j)\bmod k}$，以及把 $i$ 写成 $k$ 进制形式：$i=\overline{i_0i_1\dots i_m}(k) $后，$T_{x,i}=\Pi {j=0}^m T{x_j,i_j}$

因此只需考虑 $T_{x,i}(0\le x,i < k)$ 即可。

想到1的 $k$ 次单位根：$T_{x,i}=\omega_{k}^{xi}$

那么：$\omega _{k}^i\omega _{k}^j=\omega_k^{(i+j)\bmod k}=\omega_k^{i\bigoplus j}$

由于矩阵需要存在逆矩阵，即要求满秩。

不妨想到范德蒙德矩阵：

$$\begin{bmatrix}
1 & 1 & 1 & \dots & 1\
1 & \omega _ k^1 & \omega _ k^2 & \dots &\omega _ k^{k-1} \
1 & \omega _ k^2 & \omega _ k^4 & \dots & \omega _ k^{2(k-1)}\
\vdots & \vdots & \vdots & \dots & \vdots\
1 & \omega _ k^{k-1} & \omega _ k^{2(k-1)} & \dots & \omega _ k^{(k-1)(k-1)}
\end{bmatrix}$$

逆矩阵和fft的一样。

这样子就能做任意进制的FWT了。

难度在求单位根上。

例题

1，UVA13277

模板题没啥好说的。

2，HDU6596

模板题 $\times 2$。

3，HDU6618

3进制FWT+倍增+状压，见此

4，Distance Between Sweethearts

5，CF1119H

思维难度较大，见此

6，牛客挑战赛36G

分治FWT，见此