本文大量参考了：
- command_block 的博客：位运算卷积(FWT) & 集合幂级数
FWT 概论
定义位运算卷积：\(C[k]=\sum\limits_{i\oplus j=k}A[i]B[j]\)，记作 \(C=A*B\)，其中 $\oplus $ 为某一位运算。
设 \(A,B\) 下标的范围都是 \([0,n-1]\) 且满足 \(n\) 是 \(2\) 的幂，那么卷出来 \(C\) 的下标范围也是 \([0,n-1]\)。
为了加速位运算卷积，我们尝试构造一个像 FFT 一样的算法，把卷积转化为直接点积。
设转化矩阵为 \(c\)，即 \(FWT(A)=cA\)，\(FWT(A)[i]=\sum\limits_{j=0}^nc(i,j)A[j]\)。使其满足：
\[\begin{aligned}FWT(A)[i]\cdot FWT(B)[i]&=FWT(C)[i]\\\left(\sum_{j=0}^nc(i,j)A[j]\right)\left(\sum_{j=0}^nc(i,j)B[j]\right)&=\left(\sum_{j=0}^nc(i,j)C[j]\right)\\\sum_{j=0}^n\sum_{k=0}^nc(i,j)c(i,k)A[j]B[k]&=\sum_{j=0}^nc(i,j)\sum_{a\oplus b=j}A[a]B[b]\\\sum_{j=0}^n\sum_{k=0}^nc(i,j)c(i,k)A[j]B[k]&=\sum_{j=0}^n\sum_{k=0}^nc(i,j\oplus k)A[j]B[k]\end{aligned} \]只要满足 \(c(i,j)c(i,k)=c(i,j\oplus k)\) 即可让上式成立。
事实上我们也可以证明出必要性：由于这个式子需要对任意的 \(A,B\) 都成立（也就是说 \(A[1],\cdots,A[n],B[1],\cdots,B[n]\) 可以看成是 \(2n\) 个独立的变量），那么我们就必须要满足 \(c(i,j)c(i,k)=c(i,j\oplus k)\)。
你可能会发现这个条件和 \(i\) 并没有关系，那你可能会想：能不能先找到一个数组 \(c'\) 满足 \(c'(j)c'(k)=c'(j\oplus k)\)，然后让所有的 \(c(i,j)\) 都直接赋值为 \(c'(j)\) 就好了呢？
肯定是不行的，为了保证我们得到 \(FWT(C)=c\times C\) 后能得回 \(C\)，我们还需要满足矩阵 \(c\) 有逆。而按刚刚的构造方法得到的矩阵 \(c\) 秩为 \(1\)，没有逆。
现在的问题是我们要构造出 \(n\) 种数组 \(c'\) 使得它们都满足 \(c'(j)c'(k)=c'(j\oplus k)\)，而且要求这 \(n\) 个数组拼起来得到的矩阵有逆。
一种巧妙的构造方式是：我们先构造出对于 \(n=2\) 时满足要求的矩阵，记为 \(c_1\)。然后递推对于 \(n=2^k(k>1)\) 时满足的矩阵：\(c_k=c_1\otimes c_{k-1}\)。
其中 \(\otimes\) 为克罗内克积：对于大小为 \(n\times n\) 的矩阵 \(A\) 和大小为 \(m\times m\) 的矩阵 \(B\)，它们的克罗内克积为：
\[A\otimes B=\begin{bmatrix}A_{1,1}B&\cdots&A_{1,n}B\\\vdots &\ddots &\vdots\\A_{n,1}B&\cdots&A_{n,n}B\end{bmatrix} \]也就是说 \(c_k\) 为 \(c_1\) 的 \(k\) 级分形。设 \(n=2^m\)，最后取 \(c_{m}\) 即为我们想要的 \(c\)。
考虑这么做为什么是对的，我们需要证明两点：\(c(i,j)c(i,k)=c(i,j\oplus k)\) 和矩阵 \(c\) 有逆。
-
定理 1：\(c(i,j)c(i,k)=c(i,j\oplus k)\)。
证明：设 \(x_t\) 表示 \(x\) 在二进制下的第 \(t\) 位，通过构造方式不难证明出 \(c(i,j)=\prod\limits_{i=0}^{m-1} c_1(i_t,j_t)\)。而矩阵 \(c_1\) 是满足条件的。
\(c(i,j)=\prod\limits_{i=0}^{m-1} c_1(i_t,j_t)\) 这条式子是非常好的记忆方法：即我们先找出对 \(n=2\) 满足要求的矩阵，那么 \(c(i,j)\) 就是 \(i,j\) 拆位后各位的 \(c\) 的乘积。
在证明矩阵 \(c\) 有逆之前，我们需要了解一个有关克罗内克积的引理。
-
引理 1：对于大小为 \(n\times n\) 的矩阵 \(A\) 和大小为 \(m\times m\) 的矩阵 \(B\)，设它们的克罗内克积为 \(C=A\otimes B\)，那么有：
\[|C|=|A|^m|B|^n \]证明：考虑使用高斯消元法来求解行列式，那么 \(|A|\) 的含义就是：\((-1)^{\mu(A)}D(A)\)，其中 \(D(A)\) 表示将 \(A\) 消为上三角矩阵后对角线上元素的乘积，\(\mu(A)\) 表示消元过程中使用操作”交换两行“的次数的奇偶性。
现在考虑对 \(C\) 进行高斯消元，我们可以每 \(m\) 行一组按对 \(B\) 消元的方式消元，共 \(n\) 组，得到：（其中 \(B'\) 为将矩阵 \(B\) 消元后得到的上三角矩阵）
\[|C|=(-1)^{n\cdot \mu(B)}\left|\begin{bmatrix}A_{1,1}B'&\cdots&A_{1,n}B'\\\vdots &\ddots &\vdots\\A_{n,1}B'&\cdots&A_{n,n}B'\end{bmatrix}\right| \]然后再把每 \(m\times m\) 的矩阵看成一格，然后用对 \(A\) 消元的方式对剩下的这个 \(n\times n\) 格的矩阵消元，得到：（其中 \(A'\) 为将矩阵 \(A\) 消元后得到的上三角矩阵）
\[|C|=(-1)^{n\cdot \mu(B)}(-1)^{m\cdot \mu(A)}\left|\begin{bmatrix}A'_{1,1}B'&\cdots&A'_{1,n}B'\\\vdots &\ddots &\vdots\\A'_{n,1}B'&\cdots&A'_{n,n}B'\end{bmatrix}\right| \]最后得到的这个矩阵是一个上三角矩阵，它的对角线的乘积为 \(D(A)^mD(B)^n\)，于是：
\[\begin{aligned}|C|&=(-1)^{n\cdot \mu(B)}\times (-1)^{m\cdot \mu(A)}\times D(A)^m\times D(B)^n\\&=\left((-1)^{\mu(A)}D(A)\right)^m\left((-1)^{\mu(B)}D(B)\right)^n\\&=|A|^m|B|^n\end{aligned} \] -
定理 2：矩阵 \(c\) 有逆。
证明：矩阵有逆等价于矩阵行列式不为 \(0\)。初始时 \(c_1\) 满足条件，即 \(c_1\) 行列式不为 \(0\)。根据引理1可以归纳证明对于任意 \(k\) 都有 \(c_k\) 行列式不为 \(0\)。
至此，我们证明了我们所构造出来的 \(c\) 是满足条件的转化矩阵。
而用这种构造方式构造出的 \(c\) 的一个好处是它能用分治加速转化的过程。
假设我们现在要求 \(c_k A\)，其中 \(A\) 的下标范围为 \([0,2^k-1]\)：
根据构造方式，我们可以将 \(c_k\) 分成四块，每块都是 \(c_{k-1}\) 的若干倍（具体来说，倍数分别为 \(c_1\) 中对应的的四个数）。那么我们也将 \(A\) 分成两半 \(A_1,A_2\)，那么我们只需要求出 \(c_{k-1}A_1\) 和 \(c_{k-1}A_2\) 就能 \(O(2^k)\) 求出 \(c_kA\) 了。
于是就可以分治。具体来说，在第 \(k\) 轮时，我们将 \(0\sim n-1\) 每 \(2^k\) 分成一块，然后对于每一段 \(l\sim r(r-l+1=2^k)\)，用 \(c_{k-1}A_{l\sim mid}\) 和 \(c_{k-1}A_{mid+1\sim r}\) 一起 \(O(2^k)\) 推导得到 \(c_kA_{l\sim r}\)。
时间复杂度 \(O(n\log n)\)。
下面举几种位运算的例子。
Or 卷积
相当于要求两种线性无关的 \(c\) 使得它们都满足 \(c(j)c(k)=c(j|k)\)。我们可以先求出所有的可能的 \(c\)：（记 \(a=c(0),b=c(1)\)）
\[\begin{cases}a\cdot a=a\\a\cdot b=b\\b\cdot b=b\end{cases} \]得到 \(3\) 组解：\(\begin{cases}a=0\\b=0\end{cases},\begin{cases}a=1\\b=0\end{cases},\begin{cases}a=1\\b=1\end{cases}\)，唯一的方法是取后两组组成矩阵 \(c_1=\begin{bmatrix}1&0\\1&1\end{bmatrix}\)。
And 卷积
类似，得到 \(c_1=\begin{bmatrix}0&1\\1&1\end{bmatrix}\)。
Xor 卷积
类似，得到 \(c_1=\begin{bmatrix}1&1\\1&-1\end{bmatrix}\)。
位值域扩展
注意到：or 卷积为模 \(2\) 意义下的高维 max 卷积，and 卷积为模 \(2\) 意义下的高维 min 卷积，xor 卷积为模 \(2\) 意义下的高维加法卷积。
事实上，我们也可以用类似的方法实现模 \(k\) 意义下的高维 max/min/加法 卷积。
设 \(n=k^b\)。我们同样先构造出对于 \(n=k\) 时满足要求的 \(k\times k\) 矩阵 \(c_1\)，然后 \(c_1\) 的 \(b\) 级分形即为我们要的转化矩阵 \(c\)。同样，我们只需要证明 \(c(i,p)c(i,q)=c(i,p\oplus q)\) 且矩阵 \(c\) 有逆。
对于前者，我们类似地可以得到 \(c(i,j)=\prod_{t=0}^{b-1} c(i_t,j_t)\)，其中 \(i_t\) 为 \(i\) 在 \(k\) 进制下第 \(t\) 位的值。那么就易证了。
而关于矩阵有逆的证明则没有任何变化，因为过程中我们只用到了克罗内克积的性质。
所以按照该方法构造出来的矩阵 \(c\) 仍然是满足要求的。
仍然是分治加速求 \(c\)。在第 \(t\) 轮时，我们将序列每 \(k^t\) 分成一段，一段内用 \(O(k\cdot k^t)\) 的时间求出 \(c_tA_{l\sim r}\)。于是每一轮的时间复杂度均为 \(O(kn)\)，总时间复杂度 \(O(nk\log_kn)\)。
模 \(k\) 意义下的 max/min 卷积
先讲 max 卷积的情况。我们需要构造 \(k\) 组线性无关的 \(c\) 使得它们都满足 \(c(p)c(q)=c(\max(p,q))\)。
取 \(p=q\) 我们首先可以确定 \(c\) 的值域为 \(\{0,1\}\)。然后发现 \(c(p)c(q)=c(\max(p,q))\) 说明 \(c\) 数组肯定形如前一段是 \(1\) 后一段是 \(0\)。那么除了全 \(0\) 之外恰好就有 \(k\) 组 \(c\)。把它们按任意顺序拼成一个矩阵均可。
为了方便，一般采用形如 \(\scriptsize\begin{bmatrix}1&0&0&0\\1&1&0&0\\1&1&1&0\\1&1&1&1\end{bmatrix}\) 这种方式，其逆为 \(\scriptsize\begin{bmatrix}1&0&0&0\\-1&1&0&0\\0&-1&1&0\\0&0&-1&1\end{bmatrix}\)。
发现其本质上就是前缀和及差分，所以单次求 \(c_tA_{l\sim r}\) 的时间可以从 \(O(k\cdot k^t)\) 优化到 \(O(k^t)\)。总时间复杂度降为 \(O(n\log_kn)\)。
从更宏观的角度来说，这个过程就是在做一个高维前缀和（每一轮做了一位的前缀和）以及高维差分（每一轮做了一位的差分）。
min 卷积也是类似的，只不过 \(c\) 数组肯定形如前一段是 \(0\) 后一段是 \(1\) 罢了。
模 \(k\) 意义下的加法卷积
我们需要构造 \(k\) 组线性无关的 \(c\) 使得它们都满足 \(c(p)c(q)=c((p+q)\bmod k)\)。
直接令 \(c_1\) 为 FFT 中的范德蒙德矩阵即可，即 \(c(i,j)=w_k^{ij}\)。
但在模意义下可能不存在 \(k\) 次单位根。
咕。
标签：begin,end,运算,卷积,sum,矩阵,bmatrix,FWT From： https://www.cnblogs.com/ez-lcw/p/16843249.html