mydcwfy's Blog

集合幂级数浅谈

Posted on
Symbols count in article: 5.3k Reading time ≈ 12 mins.

有点重要的知识点，不记得省选考不考了。

1. 定义

一个长度为 $2 ^ n$ 的序列，有一个生成函数为 $F(x) = \sum_{i = 0} ^ {2 ^ n - 1}f(i) x ^ i$，这个生成函数就叫集合幂级数。

为什么叫集合幂级数呢？是因为我们可以把 $i$ 看作一个 $\{0, 1, \cdots, n - 1\}$ 的子集并状态压缩。

定义以下几个计算：

  1. 或卷积：$c(i) = \sum_{j \mid k = i}a(j)b(k)$。
  2. 与卷积：$c(i) = \sum_{j\odot k = i}a(j)b(k)$。
  3. 异或卷积：$c(i) = \sum_{j\oplus k = i}a(j)b(k)$。
  4. 子集卷积：$c(i) = \sum_{j\odot k = 0, j \mid k = i}b(j)c(k)$。

还有一些奇怪的科技，如子集 ln，子集 exp，这里先鸽了。

这些东西如果是暴力计算的话，显然是 $O(4 ^ n)$ 的，我们考虑有没有更优的做法。

2. FMT / FWT

1）FMT

定义高维前缀和为：$b(i) = \sum_{j\subseteq i}a(j)$。容易发现暴力做是 $O(3 ^ n)$ 的。

为什么叫高位前缀和呢？因为他相当于是 $n$ 维数组做前缀和，每维只有 01 两种。（所以好像就有了 $k$ 进制下的高维前缀和）

考虑如果只有 2 维，怎么做呢？

显然枚举每一维，再对该维前缀和，代码如下：

1
2
3
4
for (int i = 0; i < n; ++ i)
    for (int j = 1; j < n; ++ j) a[i][j] += a[i][j - 1];
for (int i = 1; i < n; ++ i)
    for (int j = 0; j < n; ++ j) a[i][j] += a[i - 1][j];

显然是枚举了两维，虽然和平常写法不同，但是如果手玩一下发现是对的。

扩展到 $n$ 维，我们就可以得到一个简短的代码：

1
2
3
for (int i = 0; i < n; ++ i)
    for (int j = 0; j < (1 << n); ++ j)
        if (j >> i & 1) a[j] += a[j ^ (1 << i)];

这个代码显然是 $O(n2 ^ n)$ 的。

同理，我们也可以得到高位后缀和的代码：

1
2
3
for (int i = 0; i < n; ++ i)
    for (int j = 0; j < (1 << n); ++ j)
        if (j >> i & 1) a[j ^ (1 << i)] += a[j];

高维前缀和和高维后缀和统称为快速莫比乌斯变换，简写为 FMT。

2）FWT

定义 $\displaystyle \text{FWT}(A) = \sum_{i = 0} ^ {2 ^ n - 1}x ^ i\sum_{j = 0} ^ {2 ^ n - 1}(-1) ^ {|i\odot j|}[x ^ j]A(x)$，这个东西就叫快速沃尔什变换，简写为 FWT。显然暴力计算是 $O(4 ^ n)$ 的。

类似于 FMT，我们逐维考虑。枚举每一维 $i$，假设我们枚举到 $j$ 不包含 $i$ 这一维。那么对于不包含 $i$ 的 $j$，显然会将两个都加起来，因为自己是 0，不管与谁都是 0，即 $a_j := a_j + a_{j\mid 2^i}, $，而包含 $i$ 的 $j\mid2^i$ 就不同了，如果是 $a_{j\mid 2 ^ i}$，显然贡献到 $a_{j\mid 2 ^ i}$ 就是 -1 了，即 $a_{j\mid2 ^ i}:= a_j - a_{j\mid 2 ^ i}$。

我们也可以写出代码：

1
2
3
4
5
6
for (int i = 0; i < n; ++ i)
    for (int j = 0; j < (1 << n); ++ j)
        if (j >> i & 1) {
            int x = a[j], y = a[j | (1 << i)];
            a[j] = x + y, a[j | (1 << i)] = x - y;
        }

我们还可以写出另一份代码：

1
2
3
4
5
6
7
int bit, tot = 1 << bit;
for (int mid = 1; mid < tot; mid <<= 1)
    for (int i = 0; i < tot; i += (mid << 1))
        for (int j = 0; j < mid; ++ j) {
            int x = a[i + j], y = a[i + j + mid];
            a[i + j] = x + y, a[i + j + mid] = x - y;
        }

发现和 NTT 其实是很像的。其实集合幂级数和多项式是有很多相似点的，我们这里才刚刚看到。

显然，时间复杂度为 $O(n2 ^ n)$。

3. 实现卷积

1）与卷积

考虑证明假设 $C(x) = \sum_{i = 0} ^ {2 ^ n - 1}x ^ i \sum_{j\odot k = i} [x ^ j]A(x) \times [x ^ k]B(x)$，那么对 $A, B, C$ 高位前缀和后，$C(x) = \sum_{i = 0} ^ {2 ^ n - 1}x ^ i[x ^ i]A(x) \times [x ^ i]B(x)$。

考虑每一对 $j, k$，最后 $j, k$ 一定会贡献到 $j\odot k$ 的所有子集，即 $\forall x\subseteq (j\odot k)$。而 $C$ 贡献显然也是 $\forall x\subseteq i$，这和前面的贡献是相同的。

于是我们先对 $A, B$ 高位前缀和，乘起来，再做高位前缀和的逆变换就可以得到 $C$ 了。

逆变换就将加号变为减号即可。

1
2
3
for (int i = 0; i < n; ++ i)
    for (int j = 0; j < (1 << n); ++ j)
        if (j >> i & 1) a[j] -= a[j ^ (1 << i)];

2）与卷积

考虑类似于或卷积的方法，这里不再赘述，证明留给读者。

3）异或卷积

前面已经定义了 $FWT(A)$，类似于 FMT，我们证明 $FWT(C) = FWT(A) * FWT(b)$。

还是考虑 $i, j, p$ 的贡献，$i\to p$ 的贡献显然是 $a(i)(-1) ^ {\mid p\odot i\mid }$，$j\to p$ 的贡献显然是 $b(j)(-1) ^ {\mid p\odot j\mid }$。

考虑 $i\oplus j$ 对 $p$ 的贡献，显然是 $(-1) ^ {(i\oplus j)\odot p}$。所以我们考虑证明 $(-1) ^ {\mid (i\oplus j)\odot p\mid } = (-1) ^ {\mid i\odot p\mid }(-1) ^ {\mid j\odot p\mid }$。

容易发现 $p$ 的限制就是将 $i, j$ 中 $p$ 该位为 1 的位拿出来，其余的不管，我们可以先对 $i$ 赋值为 $i\odot p$，$j$ 同理，显然最后的答案左边就是 $(-1) ^ {\mid i\oplus j\mid}$，容易发现就是 $i$ 的 1 个数和 $j$ 的 1 个数相加。左右显然相等。

逆变换还是将操作反过来即可。这里给出一种实现。

1
2
3
4
5
6
7
int tot = 1 << n;
for (int mid = 1; mid < tot; mid <<= 1)
    for (int i = 0; i < tot; i += (mid << 1))
        for (int j = 0; j < mid; ++ j) {
            int x = a[i + j], y = a[i + j + mid];
            a[i + j] = (x + y) >> 1, a[i + j + mid] = (x - y) >> 1;
        }

另外，可以像 NTT 一样实现。

1
2
3
4
5
6
7
8
int tot = 1 << n;
for (int mid = 1; mid < tot; mid <<= 1)
    for (int i = 0; i < tot; i += (mid << 1))
        for (int j = 0; j < mid; ++ j) {
            int x = a[i + j], y = a[i + j + mid];
            a[i + j] = x + y, a[i + j + mid] = x - y;
        }
for (int i = 0; i < tot; ++ i) a[i] >>= n;

4）子集卷积

先不考虑 $j\odot k = 0$ 的情况，容易发现这就是一个简单的或卷积。但是这个条件似乎不好处理。

发现当 $j, k\to j| k$ 是有贡献的，当且仅当 $\mid j\mid + \mid k\mid = \mid j|k\mid$，也就是说，我们限制的集合的大小。这启示我们按照集合大小分类。

我们考虑计算集合大小分别为 $a$ 和 $b$ 的或卷积，贡献到集合大小为 $a + b$ 的位置上。这样暴力做是 $O(n ^ 3 2 ^ n)$ 的，但是发现中间对 $a, b$ 的或卷积是由重复的，我们可以先将 $a = 0, \dots n - 1, b = 0, \dots n - 1$ 的高维前缀和后，再批量贡献到 $a + b$，再将 $a + b = 0, \dots, n - 1$ 的高维前缀和逆变换。容易发现时间复杂度是 $O(n ^ 2 2 ^ n)$ 的。代码在后面的例题。

4. 例题

T1：模板

FMT / FWT 模板

子集卷积模板 lg，子集卷积模板 LOJ

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
54
55
56
57
void base_or(int *a, int inv)
{
	for (int i = 0; i < bit; ++ i)
		for (int j = 0; j < tot; ++ j)
			if (j >> i & 1) (a[j] += a[j ^ (1 << i)] * inv) %= Mod;
	for (int j = 0; j < tot; ++ j) a[j] = (a[j] + Mod) % Mod;
}

void get_or(int *A, int *B)
{
	memcpy(a, A, sizeof(int) * tot), memcpy(b, B, sizeof(int) * tot);
	base_or(a, 1), base_or(b, 1);
	for (int i = 0; i < tot; ++ i) c[i] = (LL)a[i] * b[i] % Mod;
	base_or(c, -1);
	for (int i = 0; i < tot; ++ i) printf("%d ", c[i]);
	puts("");
}

void base_and(int *a, int inv)
{
	for (int i = 0; i < bit; ++ i)
		for (int j = tot - 1; j; -- j)
			if (j >> i & 1) (a[j ^ (1 << i)] += a[j] * inv) %= Mod;
	for (int j = 0; j < tot; ++ j) a[j] = (a[j] + Mod) % Mod;
}

void get_and(int *A, int *B)
{
	memcpy(a, A, sizeof(int) * tot), memcpy(b, B, sizeof(int) * tot);
	base_and(a, 1), base_and(b, 1);
	for (int i = 0; i < tot; ++ i) c[i] = (LL)a[i] * b[i] % Mod;
	base_and(c, -1);
	for (int i = 0; i < tot; ++ i) printf("%d ", c[i]);
	puts("");
}

void base_xor(int *a, int inv)
{
	if (inv == -1) inv = inv2;
	for (int i = 0; i < bit; ++ i)
		for (int j = 0; j < tot; ++ j) {
			if (j >> i & 1) continue;
			LL x = a[j], y = a[j | (1 << i)];
			a[j] = (x + y) % Mod * inv % Mod;
			a[j | (1 << i)] = (x - y + Mod) % Mod * inv % Mod;
		}
}

void get_xor(int *A, int *B)
{
	memcpy(a, A, sizeof(int) * tot), memcpy(b, B, sizeof(int) * tot);
	base_xor(a, 1), base_xor(b, 1);
	for (int i = 0; i < tot; ++ i) c[i] = (LL)a[i] * b[i] % Mod;
	base_xor(c, -1);
	for (int i = 0; i < tot; ++ i) printf("%d ", c[i]);
	puts("");
}
1
2
3
4
5
6
7
8
9
10
int main()
{
	for (int i = 0; i <= bit; ++ i) FWT(a[i], bit, 1), FWT(b[i], bit, 1);
	for (int i = 0; i <= bit; ++ i)
		for (int j = 0; j <= bit - i; ++ j)
			for (int k = 0; k < (1 << bit); ++ k)
				c[i + j][k] = (c[i + j][k] + (LL)a[i][k] * b[j][k]) % Mod;
	for (int i = 0; i <= bit; ++ i) FWT(c[i], bit, -1);
	return 0;
}

T2：Sum the Fibonacci

题目传送门 Codeforces

也是模板，请读者自行实现。