标签：dots 运算 cup mathscr FMT sf FWT otimes sum

快速位运算变换学习笔记

集合占位幂级数

设 \(R\) 是环，定义 \(R\langle S\rangle = {(2^S)}^R\)，同时定义 \(R\langle S\rangle\) 中的加法和乘法：

\[(a+b)(S)=a(S)+b(S)\\ (a * b)(S) = \sum_{A\otimes B=S} a(A)b(B) \]

。当 \(\otimes=\triangle\) 时，\(R\langle S \rangle\) 同构于 \(R[[S]]/(s^2 - 1 \mid s \in S)\)。当 \(\otimes=\sqcup\) 时，\(R\langle S \rangle\) 同构于 \(R[[S]]/(s^2 \mid s \in S)\)。

\(\otimes = \cup\)

考虑 \(\mathscr S_{\sf OR}[f](A) = \sum\limits_{a \subseteq A} f(a)\)，则有

\[\begin{aligned} \mathscr S_{\sf OR}[f * g](A) &= \sum_{a \cup b \subseteq A} f(a) g(b) \\ &= \sum_{a \subseteq A} \sum_{b \subseteq A} f(a) g(b) \\ &= \mathscr S_{\sf OR}[f](A) \times \mathscr S_{\sf OR}[g](A) \end{aligned} \]

。考虑将 \(2^S\) 同构于 \(\mathbb F_2^{n}\)。则 \(\mathscr S_{\sf OR}\) 相当于 \(f\) 上的前缀和操作。考虑高维前缀和算法：

当 \(n=1\) 时：显然可以得到正确结果。
当 \(n > 1\) 时：对于 \(n \notin S\) 和 \(n \in S\) 的两个集合进行 \(n-1\)-\(\mathscr S_{\sf OR}\)，再进行 \(1\)-\(\mathscr S_{\sf OR}\) 即可。求和号交换即可证明。

对于 \(\mathscr S_{\sf IOR}\)，可以在 \(n=1\) 时将 \(a+b\) 替换为 \(a-b\) 即可。

\(\otimes = \cap\)

\[\begin{aligned} (a*b)(S)&= \sum_{A \cap B = S} a(A) b(B) \\ &= \sum_{A^C \cup B^C = S^C} a(A^C) b(B^C) \\ &= (a*b)(S^C) & \text{which }\otimes=\cup \end{aligned} \]

\(\otimes=\sqcup\)

显然 \(A \cup B = A \sqcup B \iff |A \cup B|=|A|+|B|\)。 \(\sigma_i[a](A) = [|A|=i] a(A)\)，则有

\[\begin{aligned} (a*b)(S) &= \sum_{A \cup B = S} [|A|+|B|=|S|]a(A)b(B) \\ &= \sum_{i+j=|S|} \sum_{A \cup B = S} \sigma_i[a](A)\sigma_j[b](B) \\ &= \sum_{i+j=|S|} (\sigma_i[a] * \sigma_j[b])(S) & \text{which } \otimes=\cup \end{aligned} \]

最后这个式子可以在 \(R\langle S \rangle[[x]]\) 上乘积求出。由于常数较小，所以一般不使用 FFT，暴力求出。

这种卷积（如果扩展到 \(* : R[S] \times R[S] \to R[S \sqcup S]\)）和 \(R[S]\) 同态。

扩展

主要思想：

\[{\sf Poly}(a) = \sum_{i\ge0} \sigma_i[a] x^i \]

polyinv

分治 FFT 定义式：

\[f_i = \sum_{j=0}^{i-1} f_j g_{i-j} \iff {\rm OGF}[f] = \dfrac 1{1 - {\rm OGF}[g]} \]

，则我们可以通过两边同乘 \(g_0^{-1}\) 等方式得到通用 \(\Theta(n^2)\) Polyinv 计算。

在 \(R\langle S \rangle[[x]]\) 中 \(g_0\) 只有常数项，所以可以求逆。

类似地可以推导出其他操作。

应用

集合的划分计数：

TODO

\(\otimes = \triangle\)

注意到 \(A \sqcup B \equiv A \operatorname\triangle B \pmod 2\)，于是可以将其视为高维循环卷积。高维 FFT 即可，也即 \(B_0 = A_0 + A_1; B_1 = A_0 - A_1\)。

逆就是 \(\dfrac {A_0 \pm A_1}{2}\)，可以发现就是 \(\dfrac 1n\) 在每一次迭代中分解。

这个同样存在一定扩展空间。

位运算卷积与多重线性变换

多重线性变换

设 \(V_1,V_2,\dots,V_n\) 是 \(\mathbb F\) 上的线性空间，则 \(f : \prod V \to \mathbb F\) 是多重线性函数当且仅当

对于任意的 \(x_1,x_2,\dots,x_{i-1},x_{i+1},\dots,x_n\)，\(g(t) = f(x_1,x_2,\dots,x_{i-1},t,x_{i+1},\dots,x_n)\) 是线性函数

则 \((L[V_1,V_2,\dots,V_n], +, \times)\) 在 \(\mathbb F\) 上构成线性空间，其中 \(L[V_1,V_2,\dots,V_n]\) 代表所有 \(\prod V\) 上的多重线性函数。设 \(V_i\) 的线性基为 \(\epsilon_{i,j}\)，则有：

\[\begin{aligned} f(\boldsymbol v_1,\boldsymbol v_2,\dots, \boldsymbol v_n) &= f(\sum \lambda_{1,i} \epsilon_{1,i}, \sum \lambda_{2,i} \epsilon_{2,i}, \dots, \sum \lambda_{n,i} \epsilon_{n,i}) \\ &= \sum_{i_1,i_2,\dots,i_n} f(\boldsymbol \epsilon_i)\prod_j \lambda_{j,i_j} \end{aligned} \]