fwt & 集合幂级数
FWT
设 \([x^i] FWT(F) = \sum\limits_{j} c_{i,j} \times F_j\) 为 \(F\) 的一个线性变换且有 \([x^i] FWT(F) \cdot [x^i]FWT(G) = [x^i] FWT(F \oplus G)\)，其中 \([x^i](F \oplus G) = \sum\limits_{p \oplus q = i} [x^p] F \times [x^q] G\)。
即需要构造 \(c\) 使得 \(\forall i,j,k,c_{i,j} \cdot c_{i,k} = c_{i,j\oplus k}\)。
由于位运算的独立性，假设有合法的 \(c_{0/1,0/1}\)，可构造 \(c_{x,y} = \prod\limits_i c_{x_i,y_i}\)，显然可得 \(\prod\limits_{p} c_{i_p,j_p} \cdot c_{i_p,k_p} = \prod\limits_p c_{i_p,(j_p \oplus k_p)}=c_{i,j\oplus k}\)。
由于 \(FWT(F)\) 是一个线性变换，\(FWT(F) = c \times F\)，那么就有 \(c^{-1} \times FWT(F)=c^{-1} \times c \times F = F\)，只需使得 \(c\) 有逆就可实现 \(FWT\) 的逆变换。
这里给出在 or, and, xor 下常用的 \(c\) 及其逆矩阵。
- or
\(c=\begin{bmatrix}1&0\\1&1\\\end{bmatrix}\)，\(c^{-1}=\begin{bmatrix}1&0\\-1&1\\\end{bmatrix}\)
可以用 \(c_{i,j} = [j\subseteq i]\) 记忆。
- and
\(c=\begin{bmatrix}1&1\\0&1\\\end{bmatrix}\)，\(c^{-1}=\begin{bmatrix}1&-1\\0&1\\\end{bmatrix}\)
可以用 \(c_{i,j} = [i\subseteq j]\) 记忆。
- xor
\(c=\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}\)，\(c^{-1}=\begin{bmatrix}\frac{1}{2}&\frac{1}{2}\\\frac{1}{2}&-\frac{1}{2}\\\end{bmatrix}\)
即 \((-1)^{|i\&j|}\)。
代码实现如下，其中 \(m=2^n - 1\)。
for(int len = 1; len <= m; len <<= 1){
for(int i = 0; i <= m; i += len + len){
_rep(j, i, i + len - 1){
int t = f[j];
f[j] = c[0][0] * f[j] + c[0][1] * f[j + len];
f[j + len] = c[1][0] * t + c[1][1] * f[j + len];
}
}
}
FWT 的性质
-
\(FWT(F + G)=FWT(F) + FWT(G)\)
-
\(FWT(F \times G) = FWT(F) \cdot FWT(G)\)
-
\([x^k] FWT(F)=\sum\limits (-1)^{|i\& k|} F_i\)（异或意义下）。
【UNR #2】黎明前的巧克力
转化题意为给定 \(n\) 个多项式 \(F_i = 2x^{a_i}+1\)，求在 xor 意义下卷积 \(([x^0] \prod\limits_i F_i) - 1\) 的值。
先将 \(F_i\) 进行变换可得 \([x^k] FWT(F_i)= 2\cdot (-1)^{|k \& a_i|} + 1\)，那么 \([x^k] FWT(\prod\limits_i F_i) = \prod\limits_i [x^k] FWT(F_i)=\prod\limits_i (2\cdot (-1)^{|k \& a_i|} + 1)\)。
考虑设方程求得 \(2+1\) 与 \(-2+1\) 的个数，设它们分别为 \(u,v\)，显然有 \(u+v=n\)。
设多项式 \(F'_i=x^{a_i}\)，有 \(\sum [x^k] FWT(F'_i)=\sum\limits (-1)^{|k\& a_i|}=u-v\)。
根据 FWT 的线性性，有 \(\sum FWT(F_i)=FWT(\sum\limits F_i)\)，可一次 FWT 求得。
那么 \(u+v = n, u - v = [x^k]FWT(\sum\limits F_i)\)，然后就能求出 \([x^k] FWT(\prod\limits_i F_i) = 3^u \times (-1)^v\)，再做一次逆 FWT 即可求出目标多项式。
复杂度 \(\Theta(V\log V)\)。
CF1119H Triple
同理求 \([x^k] \prod FWT(x\cdot X^{a_i}+y\cdot X^{b_i} + z\cdot X^{c_i})=\prod (x \cdot (-1)^{|k\& a_i|} + y \cdot (-1)^{|k\& b_i|} + z \cdot (-1)^{|k\& c_i|})\)。
为了方便，先令 \(b'_i = b_i \oplus a_i, c'_i = c_ i \oplus a_i, a'_i = 0\)，设 \(x+y+z,x-y+z,x-y-z,x+y-z\) 的个数分别为 \(c_0,c_1,c_2,c_3\)。
有 \(c_0 + c_1 + c_2 + c_3 = n\)，同样令 \(F'_i = x^{b_i},F''_i = x^{c_i},F'''_i = x^{b_i \oplus c_i}\)。
其中 \([x^k] FWT(F'''_i) = [x^k]FWT(F')\cdot [x^k]FWT(F'')= (-1)^{|k\& b_i|} (-1)^{|k\& c_i|}\)。
然后即可列方程求解。
复杂度 \(\Theta(V\log V)\)。
集合幂级数
基本定义
定义 \(U\) 上的集合幂级数 \(f\)，\(f\) 可以看成一个每一项位 \(U\) 的子集的多项式，即 \(f=\sum\limits_{S\subseteq U} f_S \cdot x^S\)。
定义两个集合幂级数的加法 \(f+g=\sum\limits_S (f_S + g_S) x^S\)，减法同理。
集合并乘法（即 or 卷积）为 \(f*g=\sum\limits_S \sum\limits_T f_S \cdot g_T \cdot x^{S \cup T}\)，即 \((f*g)_S = \sum\limits_{L\cup R = S} f_L \cdot g_R\)。
无交并乘法（即子集卷积）为 \(f*g = \sum\limits_S \sum\limits_T [x\cap T = \empty]f_S \cdot g_T \cdot x^{S\cup T}\)，即 \((f*g)_S = \sum\limits_{L \cap R = \empty,L \cup R = S} f_L \cdot g_R\)。
对于集合并乘法，可以用 FWT 或 FMT（高维前缀和）实现，其中 \(FMT(f)_S=\sum\limits_{T \subseteq S} f_T\)。
容易证明 \(FMT(f+g)=FMT(f)+FMT(g),FMT(f*g)=FMT(f)\cdot FMT(g)\)。
对于无交并乘法，考虑设 \(F = \sum\limits_S f_S \cdot x^S \cdot y^{|S|}\)，其中 \(x\) 为集合幂级数，\(y\) 为普通的形式幂级数。对于两个集合 \(L,R\)，显然有 \(|L \cup R| \ge |L| + |R|\)，当且仅当 \(L \cap R = \empty\) 时取等。所以 \(H_n = \sum\limits_{i+j = n} F_i * G_j\)，其中 \(F_i = [y^i] F\)，暴力枚举 \(i,j\) 算 \(FWT(H_n) = \sum\limits_{i+j=n} FWT(F_i) \cdot FWT(G_j)\) 即可做到 \(\Theta(2^n n^2)\)。
集合幂级数复合
定义一个形式幂级数 \(H(x) = \sum h_i \cdot x^i\) 以及集合幂级数 \(f(x)\)，其中 \([x^0] f(x) = 0\)。
将 \(H\) 复合上 \(f\)，即 \(H(f(x))=\sum h_i \cdot f^i(x)\)，由于集合幂级数 \(f\) 的无交并乘法在 \([x^0] = 0\) 时大小会一直增加，所以 \(i\) 只有在 \(i \le n\) 时有意义，那么就有 \(H(f(x)) = \sum\limits_{i=0}^n h_i \cdot f^i(x)\)。考虑 \([x^S] H(f(x))\) 这个东西的组合意义，即把 \(S\) 分成 \(i\) 个有序不交集合，它们的权值乘积再乘上 \(h_i\) 的和。考虑先钦定这些集合划分的顺序，最后再乘上 \(i!\)。设 \(G_k\) 为加了 \(k\) 个元素的集合幂级数，那么每次就是加入一个 \(\max\limits_{i \in T} i > \max\limits_{i \in S} i\)，且 \(S,T\) 不交，贡献到 \(G'_{k+1,S \cup T}\)，或者直接 \(G_{k,S} \to G'_{k,S}\)。
具体地，设当前做到最高位为 \(c\)，那么之前的 \(G\) 中肯定只有 \(<2^c\) 的 \(x\) 有值，每个 \(G_i\) 和当前的集合幂级数 \(X_i\) 做一次子集卷积，复杂度是 \(\Theta(\sum\limits_{c=0}^n 2^c \cdot c^3=2^n n^3)\)，不可接受。
人类智慧地，我们更改 \(G_k\) 的定义为还需要加入 \(k\) 个元素的集合幂级数，这样每次需要更新的 \(G_k\) 只有 \(n-c\) 个，复杂度是 \(\Theta(\sum\limits_{c=0}^n 2^c \cdot c^2 \cdot (n-c)=2^n n^2)\)。
exp
\(\exp{f}\) 的组合意义与形式幂级数的 \(\exp\) 类似，即选择若干个无序不交集合拼成 \(S\) 的权值乘积之和。若将 \(f\) 看作连通图的形式幂级数，那么 \(\exp f\) 就是每个图的所有连通块权值乘积之和。
对于模数为质数的情况，存在较为简洁的复合方法：
考虑将子集卷积写成 or 卷积的形式，即 \(H(f)_S=\sum\limits_{i=0}^n h_i \sum\limits_{j_1 + j_2+\ldots j_i = |S|} \prod F_{j_t}\)，\(FWT(H(f))_S=\sum\limits_{i=0}^n h_i \sum\limits_{j_1 + j_2+\ldots j_i = |S|} \prod FWT(F_{j_t})_S\)，将 \(FWT_{S,*}\) 看成一个形式幂级数，容易发现其实就是这个形式幂级数和 \(H\) 复合。
序列上的 \(\exp\) 是可以 \(\Theta(n^2)\) 做的，设 \(B(x) = \exp A(x)\)，有 \(B'(x)=A'(x)B(x)\)。
展开得 \(B_{n+1}(n+1)=\sum\limits_{i=0}^n A_{i+1}(i+1)B_{n-i}\)，即 \(B_n = \dfrac{1}{n} \sum\limits_{i=1}^n B_{n-i} A_i i\)。
ln
\(\ln\) 的组合意义与 \(\exp\) 相反，假设 \(f\) 是由若干个集合合并而来的，那么 \(\ln f\) 就是每个完整的集合。若 \(f\) 为普通图的方案数，那么 \(\ln f\) 就是每个联通图的方案数。
和 \(\exp\) 类似，\(\ln\) 也有 \(\Theta(n^2)\) 递推的求法
设 \(B(x) = \ln A(x)\)，有 \(B'(x)=\dfrac{A'(x)}{A(x)}\)，即 \(B'(x) A(x)=A'(x)\)。
展开得 \(A_{n+1} (n+1)=\sum\limits_{i=0}^n B_{i+1} (i+1) A_{n-i}\)，移项得 \(B_n = \dfrac{nA_n - \sum\limits_{i=1}^{n-1} i B_i A_{n-i}}{nA_0}\)。
CTT 2020 Day 4 T1 杏仁
先把边反向，预处理 \(f_{S,i}\) 为杏仁的一条链集合为 \(S\) 开头为 \(t\) 链尾为 \(i\) 的方案数，\(g_S = \sum f_{S,i} \times c_{i,s}\)。
然后若干条链可以通过直接 \(\exp g\) 求得。然后对 \(g\) 求一次前缀和。
对于一个询问 \(u\)，若 \(u\) 是 \(t\) 直接回答 \(g_{tot} \times (2^{c_{t,s}} - 1)\)，否则直接枚举一个包含 \(u\) 的以 \(u\) 结尾的链 \(f_{S,u}\) 然后算剩余答案即可。
复杂度 \(\Theta(2^n n^2)\)。
求将全集分成 \(i\) 个子集的权值乘积
若直接枚举最高位 \(c\) 依次加最高位等于 \(c\) 的集合，每次要对 \(c\) 个集合幂级数做子集卷积，复杂度是 \(O(\sum\limits_c 2^c \cdot c^3=2^n \cdot n^3)\)。
类似复合的方法，从高到低枚举最高位，由于要求并为全集，那么最高位后面的位置肯定都必须是 \(1\)，所以只用考虑 \(\le c\) 的信息，但此时要做的卷积次数是 \(n-c\) 的，复杂度降为 \(O(\sum\limits_c 2^c \cdot c^2 \cdot (n-c)=2^n \cdot n^2)\)。
xmascon22_f Fast as Fast as Ryser
环是不影响的，但是链的个数要记录。
abc253_h We Love Forest 加强版
对每个集合用 exp 求出树的方案数，然后再用上面方法卷起来就行。
浙公网安备 33010602011771号