FWT 学习笔记

$\texttt{FWT}$ 是一种类似于 $\texttt{FFT}$ 的一种变换，它可以实现在 $O(n\log n)$ 的时间内求出

$\begin{aligned} & C_k=\sum_{i\&j=k}A_iB_j\\ & C_k=\sum_{i\vert j=k}A_iB_j\\ & C_k=\sum_{i\oplus j=k}A_iB_j \end{aligned}$

由于 $\texttt{FWT}$ 变换是一种线性变换，故满足 $\texttt{FWT}(A)+\texttt{FWT}(B)=\texttt{FWT}(A+B)$。

类似于 $\texttt{FFT}$ 的方法，先将 $A$ 补成 $2^k$ 的长度，每次将 $A$ 拆成两半，分别求 $\texttt{FWT}$ 即可。

因为 $\texttt{FWT}$ 有 $\texttt{or,and,xor}$ 三种形式，故也有三中不同的转移。

$\color{red}\texttt{FWT}_{\texttt{or}}$

$\texttt{FWT}(A)= \left\{ \begin{aligned} & A && n=0\\ & (\texttt{FWT}(A_0),\texttt{FWT}(A_0)+\texttt{FWT}(A_1)) ~~~&& n>0 \end{aligned} \right.$

感性证明就是后面的一堆需要最高位为 $0$ 的贡献，因为这是 $\texttt{or}$ 运算。

然后 $\texttt{UFWT}$ 就是把那个 $+$ 换成 $-$。

考虑证明 $\texttt{FWT}(A\vert B)=\texttt{FWT}(A)\times \texttt{FWT}(B)$。（这里的 $\times$ 是按位乘）

$\begin{aligned} \texttt{FWT}(A\vert B) &=\texttt{FWT}((A\vert B)_0,(A\vert B)_1)\\ & =\texttt{FWT}((A\vert B)_0,A_0\vert B_1+A_1\vert B_0+A_1\vert B_1)\\ & =(\texttt{FWT}(A_0\vert B_0),\texttt{FWT}(A_0\vert B_0+A_0\vert B_1+A_1\vert B_0+A_1\vert B_1))\\ & =(\texttt{FWT}(A_0)\times \texttt{FWT}(B_0),\\ \texttt{FWT}(A_0)\times \texttt{FWT}(B_0)+&\texttt{FWT}(A_0)\times \texttt{FWT}(B_1)+\texttt{FWT}(A_1)\times \texttt{FWT}(B_0)+\texttt{FWT}(A_1)\times \texttt{FWT}(B_1))\\ & =(\texttt{FWT}(A_0)\times \texttt{FWT}(B_0),(\texttt{FWT}(A_0)+\texttt{FWT}(A_1))\times (\texttt{FWT}(B_0)+\texttt{FWT}(B_1)))\\ & =(\texttt{FWT}(A_0),\texttt{FWT}(A_0+A_1))\times (\texttt{FWT}(B_0),\texttt{FWT}(B_0+B_1))\\ & =\texttt{FWT}(A)\times \texttt{FWT}(B) \end{aligned}$

void FWT_or(int *a,int n,int ty)
{
    for(int i=2;i<=n;i<<=1)
    for(int j=0,p=i>>1;j<n;j+=i)
    for(int k=j;k<j+p;k++)
    a[k+p]+=ty*a[k];
    return;
}

$\color{blue}\texttt{FWT}_{\texttt{and}}$

$\texttt{FWT}(A)= \left\{ \begin{aligned} & A && n=0\\ & (\texttt{FWT}(A_0)+\texttt{FWT}(A_1),\texttt{FWT}(A_1)) ~~~&& n>0 \end{aligned} \right.$

$\texttt{UFWT}$ 也是将 $+$ 变成 $-$，证明和上面的一样。

void FWT_and(int *a,int n,int ty)
{
    for(int i=2;i<=n;i<<=1)
    for(int j=0,p=i>>1;j<n;j+=i)
    for(int k=j;k<j+p;k++)
    a[k]+=ty*a[k+p];
    return;
}

$\color{deeppink}\texttt{FWT}_{\texttt{xor}}$

$\texttt{FWT}(A)= \left\{ \begin{aligned} & A && n=0\\ & (\texttt{FWT}(A_0)+\texttt{FWT}(A_1),(\texttt{FWT}(A_0)-\texttt{FWT}(A_1)) ~~~&& n>0 \end{aligned} \right.$

此时的 $\texttt{UFWT}$ 变成 $(\dfrac{\texttt{UFWT}(A_0)+\texttt{UFWT}(A_1)}{2},\dfrac{\texttt{UFWT}(A_0)-\texttt{UFWT}(A_1)}{2})$。懒得证了。

void FWT_xor(int *a,int n,int ty)
{
    for(int i=2;i<=n;i<<=1)
    for(int j=0,p=i>>1;j<n;j+=i)
    for(int k=j;k<j+p;k++)
    {
        int x=a[k],y=a[k+p];
        if(ty==1)a[k]=(x+y)%mod,a[k+p]=(x-y+mod)%mod;
        else a[k]=(x+y)%mod*inv2%mod,a[k+p]=(x-y+mod)%mod*inv2%mod;
    }
    return;
}