子集卷积学习笔记

前言

子集卷积，指的是 $c_i=\sum _{j\oplus k=i}{a}_j\times b_k$，其中 $\oplus$ 指的是 $\cup ,\cap ,xor$。
在这里，把 $i,j,k$ 的二进制看作集合。

或卷积

现在我们先求 $c_i=\sum _{j\cup k=i}{a}_j\times b_k$。
朴素的求法是 $O(n^2)$ 的。
我们回忆 $FFT$ 是怎么加速卷积过程的。$FFT$ 是快速得到多项式的一个点值表示，其实是找到一种变换，满足 $C_i^{\prime }=A_i^{\prime }\times B_i^{\prime }$，让它能够在 $O(n)$ 的时间内得到 $C$ 的点值表示。
在这里，我们也用这个思想。不妨令 $A^{\prime }$ 表示 $A$ 的变换。
注意到（我也不知道怎么想出来的），当 $a_i^{\prime }=\sum _{j\subseteq i}{a}_j$，$c_i^{\prime }=a_i^{\prime }\times b_i^{\prime }$。
$a_i^{\prime }$ 其实就是子集和。我们稍微证明一下。

$c_i^{\prime }=\sum _{d\subseteq i}{c}_d=\sum _{d\subseteq i}\sum _{j\cup k=d}{a}_j\times b_k=\sum _{j\cup i,k\cup i}{a}_j\times b_k=(\sum _{j\cup i}{a}_j)\times (\sum _{k\cup i}{b}_k)=a_i^{\prime }\times b_i^{\prime }$

这样的话，我们的任务就变成了，快速求 $a^{\prime },b^{\prime }$，也就是快速求 $a_i^{\prime }=\sum _{j\subseteq i}{a}_j$。

考虑长度为 $2^n$ 的序列 $a_0,a_1,...a_{2^n-1}$。
我们把它分为前一半和后一半，记为 $A_0$ 和 $A_1$。
那么 $A^{\prime }=merge(A_0^{\prime },A_0^{\prime }+A_1^{\prime })$，其中 $merge$ 指的是两个序列合并，加号指的是对应位置相加。
所以我们可以递归实现这个过程。但知道了原理后，我们就可以用自底向上的循环来实现这个过程。

代码长这样（和FFT很像，很好记）

void fwtor(int *a, int type){
	int j, R, k, mid;
	for(mid = 1; mid < n; mid <<= 1){
		for(R = mid << 1, j = 0; j < n; j += R){
			for(k = 0; k < mid; k++){
				a[j + k + mid] = (a[j + k + mid] + a[j + k] * type) % mod;
			}
		}
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

得到了 $C^{\prime }$，又该怎么还原出 $C$ 呢？把对应位置的贡献减掉就行了，其实就是把加变成减。
复杂度是 $O(nlogn)$ 的。

与卷积

求 $c_i=\sum _{j\cap k=i}{a}_j\times b_k$。
和或卷积类似，不过 $A^{\prime }=merge(A_0^{\prime }+A_1^{\prime },A_1^{\prime })$。（因为 $A^{\prime }$ 是补集和）
所以代码长这样：

void fwtand(int *a, int type){
	int j, R, k, mid;
	for(mid = 1; mid < n; mid <<= 1){
		for(R = mid << 1, j = 0; j < n; j += R){
			for(k = 0; k < mid; k++){
				a[j + k] = (a[j + k] + a[j + k + mid] * type) % mod;
			}
		}
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

异或卷积

记 $a\otimes b$ 表示 $|a\cap b|mod2$，也就是 $a,b$ 交集大小的奇偶性。
令 $FWT(A{)}_i=\sum _{j\otimes i=0}{a}_j-\sum _{j\otimes i=1}{a}_j$

不难推导（挺难推导） $FWT(C{)}_i=FWT(A{)}_i\times FWT(B{)}_i$

考虑怎么求 $FWT(A)$ 和 $IFWT(A^{\prime })$
仍然考虑分治，记前一半和后一半为 $A_0$ 和 $A_1$。
那么，考虑最终序列的 $FWT$。
考虑前面一半，由于 $A_0$ 与 $A_0$ 和 $A_1$ 取交集最高位都是 $0$，这样交集的奇偶性不会发生变化，因此前一半是 $FWT(A_0)+FWT(A_1)$。
考虑后面一半，由于 $A_0$ 与 $A_1$ 取交集最高位是 $0$，因此 $A_0$ 的贡献就是 $FWT(A_0)$，$A_1$ 与 $A_1$ 取交集最高位是 $1$（奇偶性发生了变化），因此贡献是 $-FWT(A_1)$。
所以 $FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))$
不难反推出 $IFWT(A^{\prime })$（解个二元一次方程就行了QAQ），即 $a=(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2})$
然后再从底到顶循环就行了。

代码长这样

void fwt(int *a){
	int j, R, k, mid, x, y;
	for(mid = 1; mid < n; mid <<= 1){
		for(R = mid << 1, j = 0; j < n; j += R){
			for(k = 0; k < mid; k++){
				x = a[j + k], y = a[j + k + mid];
				a[j + k] = (x + y) % mod;
				a[j + k + mid] = (x - y) % mod;
			}
		}
	}
}

void ifwt(int *a){
	int j, R, k, mid, x, y;
	for(mid = 1; mid < n; mid <<= 1){
		for(R = mid << 1, j = 0; j < n; j += R){
			for(k = 0; k < mid; k++){
				x = a[j + k], y = a[j + k + mid];
				a[j + k] = z * (x + y) * inv2 % mod;
				a[j + k + mid] = z * (x - y) * inv2 % mod;
			}
		}
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

子集卷积

现在要求 $c_i=\sum _{j\cup k=i,j\cap k=\varnothing }{a}_j\times b_k$

$j\cup k=i$，直接或卷积即可。
$j\cap k=i$，在满足第一个条件时，等价于 $|j|+|k|=|i|$。
因此，我们在或卷积的时候多开一维，具体的，令 $f_{i,s}$ 表示集合 $s$ 的所有大小为 $i$ 的子集和。
不难证明 $c_{i,s}=\sum _{j=0}^i{a}_{j,s}\times b_{i-j,s}$。
然后我们最终要求的就是 $c_{|i|,i}$。
复杂度是 $O(nlo{g}^{2}n)$。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL z = 1;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}

const int N = (1 << 21), mod = 1e9 + 9;

int n, a[21][N], b[21][N], c[21][N], sz[N];

void fwt(int *a, int type){
	int j, k, mid, R;
	for(mid = 1; mid < n; mid <<= 1){
		for(R = mid << 1, j = 0; j < n; j += R){
			for(k = 0; k < mid; k++){
				a[j + k + mid] = (a[j + k + mid] + a[j + k] * type) % mod;
			}
		}
	}
}


int main(){
	int i, j, k, m;
	for(i = 1; i < (1 << 21); i++) sz[i] = sz[i - (i & -i)] + 1;
	m = read(); n = (1 << m);
	for(i = 0; i < n; i++) a[sz[i]][i] = read();
	for(i = 0; i < n; i++) b[sz[i]][i] = read();
	for(i = 0; i <= m; i++){
		fwt(a[i], 1); 
		fwt(b[i], 1);
	}
	for(i = 0; i <= m; i++){
		for(j = 0; j <= i; j++){
			for(k = 0; k < n; k++)
				c[i][k] = (c[i][k] + z * a[j][k] * b[i - j][k] % mod) % mod;
		}
	}
	
	for(i = 0; i <= m; i++) fwt(c[i], -1);
	for(i = 0; i < n; i++){
		printf("%d ", (c[sz[i]][i] + mod) % mod);
	}
	return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53