集合幂级数

or/and/xor 卷积

对于序列 $A_{0,1,…,2^n-1},B_{0,1,…,2^n-1}$ ，其 or/and/xor 卷积 $C = A * B$ 定义为

$$C_{x} = \sum_{i \oplus j=x} A_i B_j$$

其中 $\oplus$ 分别为 or/and/xor 三种运算。

or/and 也可以看成两个集合的并/交，xor 是集合的对称差。

记多项式 $F(x) = \sum_{S \subseteq U} f_Sx^S $，那么 or/and/xor 卷积可以看成多项式乘法，这样的多项式叫集合幂级数。

Fast Mobius Transform

对于 or 卷积，枚举子集可以简单做到 $O(3^n)$。

可以先考虑一维的情况，即 $C_x = \sum_{ \max(i,j) = x} A_iB_j$。这个可以先求出 $C$ 前缀和的结果，然后差分得到 $C$。

类似地

$$\begin{aligned} \sum _{k \subseteq x} C_k &= \sum_{i \cup j \subseteq x} A_iB_j \\ &= \sum_{i \subseteq x} A_i \sum_{j \subseteq x} B_j \\ \end{aligned}$$

那么只需要计算高位前缀和和高维差分即可，时间复杂度 $O(n2^n)$。

and 卷积只需要将高维前缀和改为高维后缀和。

下面是另一种写法，做的事情是一样的。

void OR(int A[N],int op){
    for(int mid=1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j)
                mod(A[j+mid]=op*A[j]+A[j+mid]);
}
void AND(int A[N],int op){
    for(int mid=1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j)
                mod(A[j]=A[j]+op*A[j+mid]);
}

Fast Walsh Transform

xor 卷积也可以做到 $O(n2^n)$。

or/and 卷积相当于构造一个矩阵 $T$，满足 $T(A * B) = (TA) \cdot (TB)$，且 $T$ 可逆。由于 $T$ 的特殊性，$TA$ 是可以简单计算的。

推式子得到 $T$ 需要满足 $T(k,i) T(k,j) = T(k,i \oplus j)$ 且可逆。

位运算每一位是独立的，若能求出 $2 \times 2$ 的矩阵 $T’$ 满足上述限制，那么对于长为 $2^n$ 的序列，只需令 $T(i,j) = \prod_{x=0}^{n-1} T’(i_x,j_x)$ 即可。

最后得到

$$T' = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix} ,\quad T'^{-1} = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} \\ \end{bmatrix}$$ $$\mathrm{FWT}(A)[i] = \sum_{j} (-1)^{|i \cap j|} A_j \\ \mathrm{FWT}^{-1}(A) [i] = \frac{1}{2^n} \sum_{j} (-1)^{|i \cap j|} A_j$$

代码如下

void XOR(int A[N],int op){
    for(int mid=1,A0,A1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j){
                A0=A[j],A1=A[j+mid];
                mod(A[j]=A0+A1),mod(A[j+mid]=A0-A1);
                if(op==-1) A[j]=1ll*A[j]*inv2%MOD,A[j+mid]=1ll*A[j+mid]*inv2%MOD;
            }
}

例题

• 求 $\prod_i (1 + 2x^{a_i}) [0]$（黎明巧克力）

  每一位只能是 $-1/3$，考虑求出每一位上 $-1/3$ 的个数，设分别为 $x,y$。

  求出 $\sum_i \mathrm{FWT} (A_i)$，记该位的和为 $s$，有 $x+y = n,-x+3y = s$，解出来即可。

• CF1119H Triple

  求 $\prod_{i=1}^{n} \sum_{j=0}^{m} w_jx^{a_{i,j}}$，$a \in [0,2^k)$。

  可以做到 $O(nm2^m+(m+k)2^{m+k})$。

  就是 FWT 求 $\sum_i x^{\oplus_{j \in T} a_{i,j}}$，然后解方程，解方程这一步可以用 FWT 做。

子集卷积

【模板】子集卷积

就是多记一维为 $1$ 的个数。

概述

$$(x \oplus y) \& z = (x \& z) \oplus (y \& z)$$ $$\frac{1}{2^{n}} \sum_{T < 2^n} (-1)^{|S \& T|} = [S=0]$$

得到

$$\begin{aligned} h_{S} &= \sum_{L \oplus R = S} f_{L}g_{R} \\ &= \sum [L \oplus R \oplus S = 0]f_{L}g_{R} \\ &= \sum \frac{1}{2^n} \sum_{T < 2^n} (-1)^{|(L \oplus R \oplus S) \& T|} f_{L}g_{R} \\ &= \sum \frac{1}{2^n} \sum_{T < 2^n} (-1)^{|L \& T|}(-1)^{|R \& T|}(-1)^{|S \& T|}f_{L}g_{R} \\ &= \frac{1}{2^n} \sum_{T < 2^n} (-1)^{|S \& T|} (\sum_{L < 2^n}(-1)^{|L \& T|}f_{L})(\sum_{R < 2^n}(-1)^{|R \& T|}g_{R}) \end{aligned}$$

定义沃尔什变换为

$$f_{S} = \sum_{T < 2^n} (-1)^{|S \& T|} f_{T}$$

其逆变换为

$$f_{S} = \sum_{T < 2^n} (-1)^{|S \& T|} f_{T}$$

void OR(int A[N],int op){
    for(int mid=1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j)
                mod(A[j+mid]=op*A[j]+A[j+mid]);
}
void AND(int A[N],int op){
    for(int mid=1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j)
                mod(A[j]=A[j]+op*A[j+mid]);
}
void XOR(int A[N],int op){
    for(int mid=1,A0,A1;mid<(1<<n);mid<<=1)
        for(int i=0;i<(1<<n);i+=(mid<<1))
            for(int j=i;j<i+mid;++j){
                A0=A[j],A1=A[j+mid];
                mod(A[j]=A0+A1),mod(A[j+mid]=A0-A1);
                if(op==-1) A[j]=1ll*A[j]*inv2%MOD,A[j+mid]=1ll*A[j+mid]*inv2%MOD;
            }
}

Nim

nim 游戏，有 $n$ 堆石子，求每堆石子为不超过 $m$ 的素数且先手必败的方案数。

$1 \le n \le 10^9,1 \le m \le 10^5$。

先手必败当且仅当异或和为 $0$。FWT 即可，时间复杂度 $O(m\log m + m\log n)$。

连通生成子图计数

给你 $n$ 个节点的无向图 $G$，求连通生成子图个数，答案对 $10^9 + 7$ 取模。

$1 \le n \le 20$。

记 $f$ 为连通生成子图的集合幂级数，$g$ 为生成子图的集合幂级数，令$f_{\emptyset}=g_{\emptyset}=0$，$g$ 是好求的。定义乘法为子集卷积，那么 $g = \sum_{i \ge 1} \frac{f^{i}}{i!} = e^f -1$，即 $f = \ln(g+1)$。

线性基

对每个 $S \in [0,2^n)$，求 $\sum [\bigoplus_{x \in T}x = S] \prod_{x \in T} a_x \prod_{x \notin T} b_x$。

$1 \le n \le 20$。

定义乘法为异或卷积，即求 $\prod (a_i + b_i x^i)$ 的各项系数。

FWT，定义乘法为对应相乘，转化为 $\mathrm{IFWT} (\prod \mathrm{FWT} (a_i + b_ix^i))$。根据定义

$$\begin{aligned} \prod \mathrm{FWT} (a_i + b_ix^i) &= \prod_{i} \sum_{j < 2^n} (a_i+(-1)^{|j \& i|} b_i)x^j \\ &= \sum_{j < 2^n} x^j \prod_{i} (a_i + (-1)^{|j \& i|}b_i) \end{aligned}$$

即对每个 $S \in [0,2^n)$ 求出 $\prod_{i}(a_i + (-1)^{|S \& i|}b_i)$。按位考虑，记 $f_{k,S}$ 为满足 $i \oplus S \in [0,2^k)$ 的 $i$ 的上式的值。

求逆/exp/ln/开根

$$\frac{1}{1-f} = \sum_{i=0}^{\infty} f^i \\ e^f = \sum_{i=0}^{\infty} \frac{f^i}{i!}$$

求逆相当于有序组合，exp 相当于无序组合，ln 是 exp 的逆，开根目前不会用。

求逆

乘法定义为子集卷积，若 $f \times g = \epsilon$ 那么有

$$\sum_{i=0}^{n} f_i g_{n-i} = [n=0] \\ g_i = \begin{cases} \frac{1}{f_0} & i=0 \\ -\frac{1}{f_0}\sum_{j=0}^{i-1} f_{i-j}g_j & \mathrm{otherwise} \end{cases}$$

exp

$g = e^f$，为使结果收敛，需要有 $f_0=0$，那么 $g_0=1$。组合意义上也可解释，如果空集方案数不为 $0$，那么可以组合无限个空集。

两边求导得到 $g’ = f’g$，那么

$$(i+1)g_{i+1} = g'_{i} = \sum_{j} f'_{j}g_{i-j} \\ g_{i+1} = \frac{1}{i+1} \sum_{j=0}^{i} (j+1)f_{j+1}g_{i-j}$$

ln

$f = \ln g$，同样需要有 $f_0 = 0,g_0 = 1$。

$$\begin{aligned} g_{i+1} &= \frac{1}{i+1} \sum_{j=0}^{i} (j+1) f_{j+1} g_{i-j} \\ f_{i+1} &= g_{i+1} - \frac{1}{i+1} \sum_{j=0}^{i-1} (j+1)f_{j+1} g_{i-j} (i \ge 0) \\ f_{i} &= g_{i} - \frac{1}{i} \sum_{j=0}^{i-1} jf_jg_{i-j} (i \ge 1) \end{aligned}$$

开根

$g = \sqrt{f}$，那么有 $g_0 = \sqrt{f_0}$

$$\begin{aligned} g^2 &= f \\ \sum_{j=0}^{i} g_{j}g_{i-j} &= f_i \\ 2g_{i}g_{0} &= f_i - \sum_{j=1}^{i-1} g_jg_{i-j} \\ g_{i} &= \frac{1}{2g_0}(f_i - \sum_{j=1}^{i-1}g_jg_{i-j}) \end{aligned}$$

杂题

• 宿命 | Regulation of Destiny

  类三/四进制 FWT（改成 $\sum *$ 也可以做，矩阵是前缀和的形式，可能吧）

• 欧伊昔

• CF449D Jzzhu and Numbers

  • 容斥 + 高维后缀和。
  • 答案即为 $\prod_{i} (x^{U} + x^{a_i})[0]$，$(x^{U} + x^{a_i})$ FMT 后得到的值只有 $1,2$，于是可以一起 FMT，然后变成 $2^c$。