1.2.1 [学习笔记]基本子集操作

\[ \rm{Define\ \LaTeX \ Macros\ Here} \newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}} \newcommand\ul[1]{\underline{#1}} \newcommand\dis{\operatorname{dis}} \newcommand\edp{\operatorname{edp}} \newcommand\deg{\operatorname{deg}} \newcommand\pcnt{\operatorname{popcount}} \]

抄写了位运算卷积(FWT) & 集合幂级数 - command_block 和【学习笔记】子集卷积相关 - UltiMadow。

FWT¶

其实 OR, AND, XOR 三个操作都能做。不过 OR 和 AND 一般被更简单好写的 FMT 替代了。

FWT 的想法类似 FFT，是不是也有人叫这玩意多维 FFT 还是啥来着。

记 \(n=2^k\)，其中 \(k\) 是某个非负整数。

总之就是你有长度为 \(n\) 的向量 \(A\) 和 \(B\)，你希望求出同样长度为 \(n\) 的向量 \(X\)，满足

\[ X_k=\sum_{i\oplus j=k}A_i\cdot B_j \]

这里 \(\oplus\) 是某种运算。然后 FWT / FFT 的第一步想法就是，去构造一个大小为 \(n\times n\) 的可逆矩阵 \(C\)，使得有

\[ (CA)\circ (CB)=CX \]

其中 \(\circ\) 是矩阵的 Hadamard 积。

我们来仔细考察矩阵 \(C\) 的性质，第一步是先把矩阵乘法展开，\(\forall i\in [0,n)\)，下列等式成立。

\[ \qty(\sum_{j=0}^{n-1}C_{i,j}A_j)\qty(\sum_{j=0}^{n-1}C_{i,j}B_j)=\sum_{j=0}^{n-1}C_{i,j}X_j \]

左边可以直接乘法分配律

\[ \sum_{j=0}^{n-1}\sum_{k=0}^{n-1}C_{i,j}C_{i,k}A_jB_k=\sum_{j=0}^{n-1}C_{i,j}X_j \]

然后把右边的这个 \(X_j\) 也展开一下

\[ \begin{aligned} \sum_{j=0}^{n-1}\sum_{k=0}^{n-1}C_{i,j}C_{i,k}A_jB_k&=\sum_{j=0}^{n-1}C_{i,j}\sum_{t_1\oplus t_2=j}A_{t_1}B_{t_2}\\ &=\sum_{j=0}^{n-1}\sum_{t_1\oplus t_2=j}A_{t_1}B_{t_2}C_{i,t_1\oplus t_2}\\ &=\sum_{t_1=0}^{n-1}\sum_{t_2=0}^{n-1}A_{t_1}B_{t_2}C_{i,t_1\oplus t_2} \end{aligned} \]

我们就得到 \(C_{i,j}C_{i,k}=C_{i,j\oplus k}\)。因为我们的 FWT 是一个按位的卷积，所以应当可以拆位计算贡献，所以有

\[ C_{i,j}=\prod_{p}C_{i_p,j_p} \]

其中 \(i_p,j_p\) 分别表示 \(i,j\) 的第 \(p\) 个二进制位。那么我们构造一个 \(2\times 2\) 的矩阵即可。

OR 和 AND 的构造就不介绍了，具体见 cmd 的博客。考虑怎么构造 XOR 的矩阵。

\(C_{0,0}C_{0,y}=C_{0,y}\)，所以 \(C_{0,0}=1\)。
\(C_{1,1}C_{1,1}=C_{1,0}\)
\(C_{1,0}C_{1,1}=C_{1,1}\)，故 \(C_{1,0}=1\)。结合上式有 \(C_{1,1}=1\) 或 \(C_{1,1}=-1\)。
\(C_{0,1}C_{0,1}=C_{0,0}=1\)，所以 \(C_{0,1}=1\) 或 \(C_{0,1}=-1\)。
由于 \(C\) 可逆，且 \(C_{0,0}=C_{1,0}=1\)，故 \(C_{1,1}\neq C_{0,1}\)，可行的矩阵有且只有

\[ \begin{bmatrix} 1 &1\\ 1 &-1 \end{bmatrix}, \begin{bmatrix} 1 &-1\\ 1 &1 \end{bmatrix} \]

值得一提的是 cmd 这里写错了…… \(\begin{bmatrix} 1 &1\\ -1 &1 \end{bmatrix}\) 是不可行的，从提交记录 Submission#169888354 可以看出来 \(\begin{bmatrix} 1 &-1\\ 1 &1 \end{bmatrix}\) 是对的。但我们都不用这个，而是用 \(\begin{bmatrix} 1 &1\\ 1 &-1 \end{bmatrix}\)，因为它的逆就是自己乘上 \(\dfrac{1}{2}\)，可以少写两行。

类似 FFT，FWT 的一个实现是

void XOR(ll *f, ll inv) {
    for (int i = 1; i < (1 << n); i <<= 1)
        for (int j = 0; j < (1 << n); j += (i << 1))
            for (int k = 0; k < i; k++) {
                ll x = f[j + k], y = f[i + j + k];
                f[j + k] = (x + y) * inv % mod;
                f[i + j + k] = (x - y + mod) * inv % mod;
            }
}

子集卷积¶

你说得对，但你说的不对。

给你两个长度为 \(2^k\) 的向量 \(A,B\)，求出 \(X\)，其中

\[ X_k=\sum_{\substack{i\operatorname{or}j=k \\ i\operatorname{and}j=0}}A_iB_j \]

问题就是这个 \(i\operatorname{and} j=0\) 的限制很棘手，我们希望把它刻画成另一个与位相关的限制。

因为限制代表着不会进位，所以我们有 \(\pcnt(i)+\pcnt(j)=\pcnt(i\operatorname{or}j)\)。

我们按 \(\pcnt(i)\) 将 \(A,B,C\) 分为 \(\log n\) 个序列，第 \(k\) 个序列中第 \(s\) 个位置 \(A_{k,s}=A_{s}\) 当且仅当 \(\pcnt(s)=k\)，否则这一位为 \(0\)。\(B\) 的 \(\log\) 个序列同理。我们分别对这 \(\log\) 个序列分别 FMT，然后 \(A\) 的第 \(i\) 个序列和 \(B\) 的第 \(j\) 个序列贡献到 \(C\) 的第 \(i+j\) 个序列。复杂度 \(\mathcal O(n^22^n)\)。

一个实现。