使用矩阵和张量积构造 FWT

对于位运算卷积

C_k=\sum_{i\circ j=k}A_iB_j,

其中 $\circ$ 可以是 OR、AND 或 XOR。我们希望构造一个线性变换 $F$ ，使卷积在变换后变成逐点乘法：

F(C)_i=F(A)_iF(B)_i.

于是可以按照下面的流程计算卷积：

分别对 $A,B$ 做 FWT；
将变换后的数组逐点相乘；
对结果做逆 FWT，还原出 $C$ 。

下面分别推导 OR、AND 和 XOR 卷积对应的变换。

OR 卷积

1. 推导矩阵需要满足的条件

OR 卷积定义为

C_k=\sum_{x\lor y=k}A_xB_y.

设线性变换

F(A)=MA,

其中矩阵 $M$ 的第 $i$ 行、第 $k$ 列为 $m_{i,k}$ ，则

F(C)_i=\sum_km_{i,k}C_k.

代入 $C_k$ 的定义：

\begin{aligned} F(C)_i &=\sum_km_{i,k}\left(\sum_{x\lor y=k}A_xB_y\right)\\ &=\sum_x\sum_y m_{i,x\lor y}A_xB_y. \end{aligned}

因此，左边多项式中 $A_xB_y$ 的系数为

m_{i,x\lor y}.

另一方面，

\begin{aligned} F(A)_iF(B)_i &=\left(\sum_xm_{i,x}A_x\right) \left(\sum_ym_{i,y}B_y\right)\\ &=\sum_x\sum_y m_{i,x}m_{i,y}A_xB_y. \end{aligned}

右边多项式中 $A_xB_y$ 的系数为

m_{i,x}m_{i,y}.

为了使

F(C)_i=F(A)_iF(B)_i

对任意数组 $A,B$ 恒成立，对应项的系数必须相等。因此矩阵需要满足

\boxed{m_{i,x\lor y}=m_{i,x}m_{i,y}}.

2. 求一位二进制下的变换矩阵

先只考虑一位二进制，即数组长度为 $2$ ，下标只有 $0,1$ 。设

M_1= \begin{bmatrix} m_{0,0}&m_{0,1}\\ m_{1,0}&m_{1,1} \end{bmatrix}.

对于任意一行 $i$ ：

当 $x=0,y=0$ 时，

m_{i,0\lor0}=m_{i,0}^2,

即

m_{i,0}=m_{i,0}^2.

在通常使用的数域或模质数域中，解为 $m_{i,0}=0$ 或 $1$ 。

如果 $m_{i,0}=0$ ，那么对任意 $x$ 都有

m_{i,x}=m_{i,0\lor x}=m_{i,0}m_{i,x}=0,

这一整行都会变成零，矩阵不可能可逆。因此必须取

m_{i,0}=1.

当 $x=1,y=1$ 时，

m_{i,1\lor1}=m_{i,1}^2,

即

m_{i,1}=m_{i,1}^2,

所以 $m_{i,1}=0$ 或 $1$ 。

因此每一行只能是 $[1,0]$ 或 $[1,1]$ 。为了使矩阵可逆，取这两个不同的行：

\boxed{ M_1= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix} }.

3. 从一位推广到多位

由于不同二进制位之间互相独立，$n$ 位变换矩阵就是 $M_1$ 的 $n$ 次张量积：

M_n=M_1^{\otimes n}.

提取最高位，有

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix} \otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&0\\ M_{n-1}&M_{n-1} \end{bmatrix}. \end{aligned}

将长度为 $2^n$ 的数组按照最高位分成前后两半：

A= \begin{bmatrix} A_0\\ A_1 \end{bmatrix}.

于是

\begin{aligned} F(A) &=M_nA\\ &= \begin{bmatrix} M_{n-1}&0\\ M_{n-1}&M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} M_{n-1}A_0\\ M_{n-1}A_0+M_{n-1}A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)\\ F(A_0)+F(A_1) \end{bmatrix}. \end{aligned}

因此每一级的蝶形操作为

\boxed{(x,y)\longmapsto(x,x+y)}.

设数组长度为 $N=2^n$ ，递归式为

T(N)=2T\left(\frac N2\right)+O(N)=O(N\log N)=O(n2^n).

4. OR 逆变换

一位矩阵的逆为

M_1^{-1}= \begin{bmatrix} 1&0\\ -1&1 \end{bmatrix}.

又因为张量积的逆等于各矩阵逆的张量积，所以

M_n^{-1}= \begin{bmatrix} M_{n-1}^{-1}&0\\ -M_{n-1}^{-1}&M_{n-1}^{-1} \end{bmatrix}.

对应的逆蝶形操作为

\boxed{(x,y)\longmapsto(x,y-x)}.

递归实现：

CodeBlock Loading...

非递归实现：

CodeBlock Loading...

AND 卷积

AND 卷积定义为

C_k=\sum_{x\land y=k}A_xB_y.

完全同理，矩阵需要满足

\boxed{m_{i,x\land y}=m_{i,x}m_{i,y}}.

1. 一位变换矩阵

AND 的单位元是 $1$ 。对于非零的一行，必须有 $m_{i,1}=1$ ；而 $m_{i,0}$ 可以取 $0$ 或 $1$ 。因此两种不同的行是

[1,1],\qquad[0,1].

取它们组成可逆矩阵：

\boxed{ M_1= \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix} }.

2. 推广到多位

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ 0&M_{n-1} \end{bmatrix}. \end{aligned}

于是

\begin{aligned} F(A) &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ 0&M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)+F(A_1)\\ F(A_1) \end{bmatrix}. \end{aligned}

因此 AND 变换的蝶形操作为

\boxed{(x,y)\longmapsto(x+y,y)}.

3. AND 逆变换

M_1^{-1}= \begin{bmatrix} 1&-1\\ 0&1 \end{bmatrix}.

因此逆蝶形操作为

\boxed{(x,y)\longmapsto(x-y,y)}.

实现：

CodeBlock Loading...

XOR 卷积

XOR 卷积定义为

C_k=\sum_{x\oplus y=k}A_xB_y.

矩阵需要满足

\boxed{m_{i,x\oplus y}=m_{i,x}m_{i,y}}.

1. 一位变换矩阵

当 $x=0,y=0$ 时，

m_{i,0}=m_{i,0}^2.

为了避免整行退化为零，取

m_{i,0}=1.

当 $x=1,y=1$ 时，

m_{i,1\oplus1}=m_{i,1}^2,

所以

m_{i,0}=m_{i,1}^2.

由于 $m_{i,0}=1$ ，有

m_{i,1}=1\quad\text{或}\quad-1.

取两种不同的行组成矩阵：

\boxed{ M_1= \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix} }.

2. 推广到多位

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ M_{n-1}&-M_{n-1} \end{bmatrix}. \end{aligned}

于是

\begin{aligned} F(A) &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ M_{n-1}&-M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)+F(A_1)\\ F(A_0)-F(A_1) \end{bmatrix}. \end{aligned}

因此 XOR 变换的蝶形操作为

\boxed{(x,y)\longmapsto(x+y,x-y)}.

3. XOR 逆变换

一位矩阵的逆为

M_1^{-1}= \frac12 \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix}.

因此逆蝶形操作为

\boxed{(x,y)\longmapsto\left(\frac{x+y}{2},\frac{x-y}{2}\right)}.

每一层都除以 $2$ ，总共经过 $n$ 层，所以整个逆变换等价于最后统一乘上 $2^{-n}$ 。

如果在模意义下计算，需要保证 $2$ 存在乘法逆元；例如模数为奇质数时，可以预处理

i2=2^{-1}.

实现：

CodeBlock Loading...

总结

设当前处理的一对数为 $(x,y)$ ：

卷积	正变换	逆变换
OR	$(x,y)\mapsto(x,x+y)$	$(x,y)\mapsto(x,y-x)$
AND	$(x,y)\mapsto(x+y,y)$	$(x,y)\mapsto(x-y,y)$
XOR	$(x,y)\mapsto(x+y,x-y)$	$(x,y)\mapsto\left(\frac{x+y}{2},\frac{x-y}{2}\right)$

三种 FWT 的时间复杂度均为

\boxed{O(n2^n)=O(N\log N)},\qquad N=2^n.

对于位运算卷积

C_k=\sum_{i\circ j=k}A_iB_j,

其中 $\circ$ 可以是 OR、AND 或 XOR。我们希望构造一个线性变换 $F$ ，使卷积在变换后变成逐点乘法：

F(C)_i=F(A)_iF(B)_i.

于是可以按照下面的流程计算卷积：

分别对 $A,B$ 做 FWT；
将变换后的数组逐点相乘；
对结果做逆 FWT，还原出 $C$ 。

下面分别推导 OR、AND 和 XOR 卷积对应的变换。

OR 卷积

1. 推导矩阵需要满足的条件

OR 卷积定义为

C_k=\sum_{x\lor y=k}A_xB_y.

设线性变换

F(A)=MA,

其中矩阵 $M$ 的第 $i$ 行、第 $k$ 列为 $m_{i,k}$ ，则

F(C)_i=\sum_km_{i,k}C_k.

代入 $C_k$ 的定义：

\begin{aligned} F(C)_i &=\sum_km_{i,k}\left(\sum_{x\lor y=k}A_xB_y\right)\\ &=\sum_x\sum_y m_{i,x\lor y}A_xB_y. \end{aligned}

因此，左边多项式中 $A_xB_y$ 的系数为

m_{i,x\lor y}.

另一方面，

\begin{aligned} F(A)_iF(B)_i &=\left(\sum_xm_{i,x}A_x\right) \left(\sum_ym_{i,y}B_y\right)\\ &=\sum_x\sum_y m_{i,x}m_{i,y}A_xB_y. \end{aligned}

右边多项式中 $A_xB_y$ 的系数为

m_{i,x}m_{i,y}.

为了使

F(C)_i=F(A)_iF(B)_i

对任意数组 $A,B$ 恒成立，对应项的系数必须相等。因此矩阵需要满足

\boxed{m_{i,x\lor y}=m_{i,x}m_{i,y}}.

2. 求一位二进制下的变换矩阵

先只考虑一位二进制，即数组长度为 $2$ ，下标只有 $0,1$ 。设

M_1= \begin{bmatrix} m_{0,0}&m_{0,1}\\ m_{1,0}&m_{1,1} \end{bmatrix}.

对于任意一行 $i$ ：

当 $x=0,y=0$ 时，

m_{i,0\lor0}=m_{i,0}^2,

即

m_{i,0}=m_{i,0}^2.

在通常使用的数域或模质数域中，解为 $m_{i,0}=0$ 或 $1$ 。

如果 $m_{i,0}=0$ ，那么对任意 $x$ 都有

m_{i,x}=m_{i,0\lor x}=m_{i,0}m_{i,x}=0,

这一整行都会变成零，矩阵不可能可逆。因此必须取

m_{i,0}=1.

当 $x=1,y=1$ 时，

m_{i,1\lor1}=m_{i,1}^2,

即

m_{i,1}=m_{i,1}^2,

所以 $m_{i,1}=0$ 或 $1$ 。

因此每一行只能是 $[1,0]$ 或 $[1,1]$ 。为了使矩阵可逆，取这两个不同的行：

\boxed{ M_1= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix} }.

3. 从一位推广到多位

由于不同二进制位之间互相独立，$n$ 位变换矩阵就是 $M_1$ 的 $n$ 次张量积：

M_n=M_1^{\otimes n}.

提取最高位，有

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix} \otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&0\\ M_{n-1}&M_{n-1} \end{bmatrix}. \end{aligned}

将长度为 $2^n$ 的数组按照最高位分成前后两半：

A= \begin{bmatrix} A_0\\ A_1 \end{bmatrix}.

于是

\begin{aligned} F(A) &=M_nA\\ &= \begin{bmatrix} M_{n-1}&0\\ M_{n-1}&M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} M_{n-1}A_0\\ M_{n-1}A_0+M_{n-1}A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)\\ F(A_0)+F(A_1) \end{bmatrix}. \end{aligned}

因此每一级的蝶形操作为

\boxed{(x,y)\longmapsto(x,x+y)}.

设数组长度为 $N=2^n$ ，递归式为

T(N)=2T\left(\frac N2\right)+O(N)=O(N\log N)=O(n2^n).

4. OR 逆变换

一位矩阵的逆为

M_1^{-1}= \begin{bmatrix} 1&0\\ -1&1 \end{bmatrix}.

又因为张量积的逆等于各矩阵逆的张量积，所以

M_n^{-1}= \begin{bmatrix} M_{n-1}^{-1}&0\\ -M_{n-1}^{-1}&M_{n-1}^{-1} \end{bmatrix}.

对应的逆蝶形操作为

\boxed{(x,y)\longmapsto(x,y-x)}.

递归实现：

CPP

void OR(int l, int r, int opt)
{
    if(l == r) return;
    int mid = (l + r) >> 1;
    OR(l, mid, opt);
    OR(mid + 1, r, opt);
    int len = mid - l + 1;
    rep(i, l, mid)
    {
        if(opt == 1) a[i + len] += a[i];
        else a[i + len] -= a[i];
    }
}

CodeBlock Loading...

非递归实现：

CPP

void OR(Z *f, int opt)
{
    for(int i = 1; i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)
            rep(k, 0, i - 1)
                if(opt == 1) f[j + i + k] += f[j + k];
                else f[j + i + k] -= f[j + k];
}

CodeBlock Loading...

AND 卷积

AND 卷积定义为

C_k=\sum_{x\land y=k}A_xB_y.

完全同理，矩阵需要满足

\boxed{m_{i,x\land y}=m_{i,x}m_{i,y}}.

1. 一位变换矩阵

AND 的单位元是 $1$ 。对于非零的一行，必须有 $m_{i,1}=1$ ；而 $m_{i,0}$ 可以取 $0$ 或 $1$ 。因此两种不同的行是

[1,1],\qquad[0,1].

取它们组成可逆矩阵：

\boxed{ M_1= \begin{bmatrix} 1&1\\ 0&1 \end{bmatrix} }.

2. 推广到多位

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ 0&M_{n-1} \end{bmatrix}. \end{aligned}

于是

\begin{aligned} F(A) &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ 0&M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)+F(A_1)\\ F(A_1) \end{bmatrix}. \end{aligned}

因此 AND 变换的蝶形操作为

\boxed{(x,y)\longmapsto(x+y,y)}.

3. AND 逆变换

M_1^{-1}= \begin{bmatrix} 1&-1\\ 0&1 \end{bmatrix}.

因此逆蝶形操作为

\boxed{(x,y)\longmapsto(x-y,y)}.

实现：

CPP

void AND(Z *f, int opt)
{
    for(int i = 1; i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)
            rep(k, 0, i - 1)
                if(opt == 1) f[j + k] += f[j + i + k];
                else f[j + k] -= f[j + i + k];
}

CodeBlock Loading...

XOR 卷积

XOR 卷积定义为

C_k=\sum_{x\oplus y=k}A_xB_y.

矩阵需要满足

\boxed{m_{i,x\oplus y}=m_{i,x}m_{i,y}}.

1. 一位变换矩阵

当 $x=0,y=0$ 时，

m_{i,0}=m_{i,0}^2.

为了避免整行退化为零，取

m_{i,0}=1.

当 $x=1,y=1$ 时，

m_{i,1\oplus1}=m_{i,1}^2,

所以

m_{i,0}=m_{i,1}^2.

由于 $m_{i,0}=1$ ，有

m_{i,1}=1\quad\text{或}\quad-1.

取两种不同的行组成矩阵：

\boxed{ M_1= \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix} }.

2. 推广到多位

\begin{aligned} M_n &=M_1\otimes M_{n-1}\\ &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ M_{n-1}&-M_{n-1} \end{bmatrix}. \end{aligned}

于是

\begin{aligned} F(A) &= \begin{bmatrix} M_{n-1}&M_{n-1}\\ M_{n-1}&-M_{n-1} \end{bmatrix} \begin{bmatrix} A_0\\ A_1 \end{bmatrix}\\ &= \begin{bmatrix} F(A_0)+F(A_1)\\ F(A_0)-F(A_1) \end{bmatrix}. \end{aligned}

因此 XOR 变换的蝶形操作为

\boxed{(x,y)\longmapsto(x+y,x-y)}.

3. XOR 逆变换

一位矩阵的逆为

M_1^{-1}= \frac12 \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix}.

因此逆蝶形操作为

\boxed{(x,y)\longmapsto\left(\frac{x+y}{2},\frac{x-y}{2}\right)}.

每一层都除以 $2$ ，总共经过 $n$ 层，所以整个逆变换等价于最后统一乘上 $2^{-n}$ 。

如果在模意义下计算，需要保证 $2$ 存在乘法逆元；例如模数为奇质数时，可以预处理

i2=2^{-1}.

实现：

CPP

void XOR(Z *f, int opt)
{
    for(int i = 1; i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)
            rep(k, 0, i - 1)
            {
                Z x = f[j + k], y = f[j + i + k];
                f[j + k] = x + y;
                f[j + i + k] = x - y;
                if(opt == -1)
                {
                    f[j + k] *= i2;
                    f[j + i + k] *= i2;
                }
            }
}

CodeBlock Loading...

总结

设当前处理的一对数为 $(x,y)$ ：

卷积	正变换	逆变换
OR	$(x,y)\mapsto(x,x+y)$	$(x,y)\mapsto(x,y-x)$
AND	$(x,y)\mapsto(x+y,y)$	$(x,y)\mapsto(x-y,y)$
XOR	$(x,y)\mapsto(x+y,x-y)$	$(x,y)\mapsto\left(\frac{x+y}{2},\frac{x-y}{2}\right)$

三种 FWT 的时间复杂度均为

\boxed{O(n2^n)=O(N\log N)},\qquad N=2^n.