题解 P4717 【【模板】快速沃尔什变换 (FWT)】

· · 题解

所谓 \lceil\mathsf{FWT}\rfloor 主要就是构造一种 可逆 的 快速 的 变换 F 使 F(C)=F(A)\cdot F(B)，以 快速解决 某些 下标位运算卷积 的问题。
（C=A\cdot B 指 \forall i\ \ \ C_i=A_i\times B_i）

求

\forall i\ \ \ C_i=\sum_{j|k=i}A_jB_k

设 T'=F(T) 使 \forall i\ \ \ T'_ i=\sum\limits_{j|i=i}T_j。（即其 下标的所有子集处 的值的和）

由于 j|i=i,k|i=i\Rightarrow (j|k)|i=i（j 是 i 的子集，k 是 i 的子集，那么 j\cup k 也是 i 的子集），
则有 \forall i,

\large\begin{aligned}&F(A)_ i\times F(B)_ i\\=&\left(\sum_{j|i=i}A_j\right)\left(\sum_{k|i=i}B_k\right)\\=&\sum_{j|i=i}\sum_{k|i=i}A_jB_k\\=&\sum_{(j|k)|i=i}A_jB_k\\=&F(C)_ i\end{aligned}

得证 F(C)=F(A)\cdot F(B)。

快速进行变换 F：
性质 1：二进制下每 2^i 个数前 i 位（第 0 \sim i-1 位）对应相同。
证明：x\equiv x+2^i \pmod {2^i}。
性质 2：二进制下相差 2^i 的两数第 i 位相异。
证明：\left\lfloor\dfrac {x+2^i}{2^i}\right\rfloor\equiv\left\lfloor\dfrac {x\oplus2^i}{2^i}\right\rfloor \pmod 2。

设 F_0(A) 表示二进制最高位（第 i 位）为 0 的数（前 2^{i-1} 个数）仅考虑前 i-1 位的答案，F_1(A) 表示最高位为 1 的数（后 2^{i-1} 个数）仅考虑前 i-1 位的答案，则

F(A)=F_0(A),F_0(A)+F_1(A)

（其中 + 表示对应位相加）
证明：对于前 2^{i-1} 个数，其最高位为 0，其子集不会有最高位为 1 的数，所以答案与后面无关；
对于后 2^{i-1} 个数（\forall x），其最高位为 1，是 x-2^i 子集的也一定是 x 的子集，所以要加上 x-2^i 位的答案。

同理，逆变换就是把加的反着减掉就好。

具体实现就是枚举 i，枚举每一段数，在前一半和后一半之间做贡献。

代码： 

void FWTor(int a[],int type)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    (a[j|(1<<i-1)|k]+=(a[j|k]*type+p)%p)%=p;
}

求

\forall i\ \ \ C_i=\sum_{j\&k=i}A_jB_k

类似或，与就是把子集变成超集再推一遍就好，这里省略不谈。

设 T'=F(T) 使 \forall i\ \ \ T'_ i=\sum\limits_{j\&i=i}T_j。

F(A)=F_0(A)+F_1(A),F_1(A) 
void FWTand(int a[],int type)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    (a[j|k]+=(a[j|(1<<i-1)|k]*type+p)%p)%=p;
}

求

\forall i\ \ \ C_i=\sum_{j\oplus k=i}A_jB_k

（\oplus 表示异或）

异或比较麻烦，因为其不能像与和或那样简单地用子集关系表示。

设 i\circ j=\operatorname{popcount}(i\&j)\bmod 2，则有

(i\circ j) \oplus(i \circ k)=i\circ(j\oplus k)

证明：

\Leftrightarrow\operatorname{popcount}(i\&j)\oplus\operatorname{popcount}(i\&k)\equiv\operatorname{popcount}(i\&(j\oplus k)) \pmod 2 \Leftrightarrow\operatorname{popcount}(i\&j)+\operatorname{popcount}(i\&k)\equiv\operatorname{popcount}(i\&(j\oplus k)) \pmod 2

设 x=i\&j,y=i\&k,z=i\&(j\oplus k)

$x$ 的第 $p$ 位为 $1$，$y$ 的第 $p$ 位为 $1$，则 $z$ 的第 $p$ 位为 $0$（$j,k$ 都有异或无），$1+1\equiv0\pmod2$ ； $x$ 的第 $p$ 位为 $0$，$y$ 的第 $p$ 位为 $1$，则 $z$ 的第 $p$ 位为 $1$（$j,k$ 相异异或有），$0+1\equiv1\pmod2$ ； $x$ 的第 $p$ 位为 $1$，$y$ 的第 $p$ 位为 $0$，则 $z$ 的第 $p$ 位为 $1$（$j,k$ 相异异或有），$1+0\equiv1\pmod2$ ； $x$ 的第 $p$ 位为 $0$，$y$ 的第 $p$ 位为 $0$，则 $z$ 的第 $p$ 位为 $0$（$j,k$ 都无异或无），$0+0\equiv0\pmod2$ 。 于是得证。 设 $T'=F(T)$ 使 $\forall i\ \ \ T'_ i=\sum\limits_{j\circ i=0}T_j-\sum\limits_{j\circ i=1}T_j

那么有 \forall i,

\large\begin{aligned}&F(A)_ i\times F(B)_ i\\=&\left(\sum_{j\circ i=0}A_j-\sum_{j\circ i=1}A_j\right)\left(\sum_{k\circ i=0}B_k-\sum_{k\circ i=1}B_k\right)\\=&\left(\sum_{j\circ i=0}\sum_{k\circ i=0}A_jB_k+\sum_{j\circ i=1}\sum_{k\circ i=1}A_jB_k\right)-\left(\sum_{j\circ i=0}\sum_{k\circ i=1}A_jB_k+\sum_{j\circ i=1}\sum_{k\circ i=0}A_jB_k\right)\\=&\left(\sum_{(j\oplus k)\circ i=0\oplus0}A_jB_k+\sum_{(j\oplus k)\circ i=1\oplus1}A_jB_k\right)-\left(\sum_{(j\oplus k)\circ i=0\oplus1}A_jB_k+\sum_{(j\oplus k)\circ i=1\oplus0}A_jB_k\right)\\=&\sum_{(j\oplus k)\circ i=0}A_jB_k-\sum_{(j\oplus k)\circ i=1}A_jB_k\\=&F(C)_ i\end{aligned}

得证 F(C)=F(A)\cdot F(B)。

快速进行变换 F：
同样设 F_0(A) 表示二进制最高位（第 i 位）为 0 的数（前 2^{i-1} 个数）仅考虑前 i-1 位的答案，F_1(A) 表示最高位为 1 的数（后 2^{i-1} 个数）仅考虑前 i-1 位的答案，则

F(A)=F_0(A)+F_1(A),F_0(A)-F_1(A)

证明：由于最高位原先默认为 0（或者说不考虑），
对于前 2^{i-1} 个数这一位 0\&0=0,0\&1=0，不变；
对于后 2^{i-1} 个数这一位 1\&0=0,1\&1=1，由于 1 与 0 不同，于是 \circ 运算结果改变，差值与原先相反，所以是 -F_1(A)。

同理逆变换就是反过来

F'(A')=\frac{F'_ 0(A')+F'_ 1(A')}2,\frac{F'_ 0(A')-F'_ 1(A')}2 
void FWTxor(int a[],long long type)
{
    int i,j,k,x,y;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    x=(a[j|k]+a[j|(1<<i-1)|k])*type%p,
    y=(a[j|k]-a[j|(1<<i-1)|k]+p)*type%p,
    a[j|k]=x,a[j|(1<<i-1)|k]=y;
}

附本题代码完全版： 

#include<cstdio>
#include<cstring>
const int N=(1<<17)+10,p=998244353;
int n,a[N],b[N],ta[N],tb[N];
void FWTor(int a[],int type)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    (a[j|(1<<i-1)|k]+=(a[j|k]*type+p)%p)%=p;
}
void FWTand(int a[],int type)
{
    int i,j,k;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    (a[j|k]+=(a[j|(1<<i-1)|k]*type+p)%p)%=p;
}
void FWTxor(int a[],long long type)
{
    int i,j,k,x,y;
    for(i=1;i<=n;i++)
    for(j=0;j<(1<<n);j+=1<<i)
    for(k=0;k<(1<<i-1);k++)
    x=(a[j|k]+a[j|(1<<i-1)|k])*type%p,
    y=(a[j|k]-a[j|(1<<i-1)|k]+p)*type%p,
    a[j|k]=x,a[j|(1<<i-1)|k]=y;
}
int main()
{
    int i;scanf("%d",&n);
    for(i=0;i<(1<<n);i++)scanf("%d",&a[i]),a[i]%=p;
    for(i=0;i<(1<<n);i++)scanf("%d",&b[i]),b[i]%=p;
    //or
    memcpy(ta,a,sizeof a);memcpy(tb,b,sizeof b);
    FWTor(ta,1);FWTor(tb,1);
    for(i=0;i<(1<<n);i++)ta[i]=(long long)ta[i]*tb[i]%p;
    FWTor(ta,-1);
    for(i=0;i<(1<<n);i++)printf("%d ",ta[i]);putchar('\n');
    //and
    memcpy(ta,a,sizeof a);memcpy(tb,b,sizeof b);
    FWTand(ta,1);FWTand(tb,1);
    for(i=0;i<(1<<n);i++)ta[i]=(long long)ta[i]*tb[i]%p;
    FWTand(ta,-1);
    for(i=0;i<(1<<n);i++)printf("%d ",ta[i]);putchar('\n');
    //xor
    memcpy(ta,a,sizeof a);memcpy(tb,b,sizeof b);
    FWTxor(ta,1);FWTxor(tb,1);
    for(i=0;i<(1<<n);i++)ta[i]=(long long)ta[i]*tb[i]%p;
    FWTxor(ta,(p+1)>>1);
    for(i=0;i<(1<<n);i++)printf("%d ",ta[i]);putchar('\n');
    return 0;
}