子集和变换

输入一个长度为 8 的数组 a[0] ... a[7]
0 000 {}
1 001 {0}
2 010 {1}
3 011 {0, 1}
4 100 {2}
5 101 {0, 2}
6 110 {1, 2}
7 111 {0, 1, 2}
210

输出一个长度为 8 的数组，其中第i项，表示i的所有子集之和 如果 j 满足 (i&j) == j 那么 j 是 i 的子集
0: a[0]
1: a[1] + a[0]
2: a[2] + a[0]
3: a[3] + a[2] + a[1] + a[0]
4: a[4] + a[0]
5: a[5] + a[4] + a[1] + a[0]
6: a[6] + a[4] + a[2] + a[0]
7: a[7] + a[6] + a[5] + a[4] + a[3] + a[2] + a[1] + a[0]

输入数组大小是 n = 2**m

直接暴力 4**m = n^2

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		if ((i & j) == j)
		{
			b[i] += a[j];
		}
	}
}

枚举子集 3**m = n ** (log(3) / log(2) = n ** 1.58)

for (int i = 0; i < n; i++)
{
	for (int j = i;; --j &= i)
	{
		b[i] += a[j];
		if (j == 0)
		{
			break;
		}
	}
}

子集和变换 2**m * m = n log n

0
1
2
3
4
5
6
7

0
1 0
2
3 2
4
5 4
6
7 6

0
1 0
2 0
3 2 1 0
4
5 4
6 4
7 6 5 4

0
1 0
2 0
3 2 1 0
4 0
5 4 1 0
6 4 2 0
7 6 5 4 3 2 1 0

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

逆变换
for (int j = 0; j < m; j++)
{
	for (int i = 0; i < n; i++)
	{
		if (i >> j & 1)
		{
			a[i] -= a[i ^ (1 << j)];
		}
	}
}
有的人习惯倒序j，倒序i，其实无所谓


子集和变换，还有可能是0的位置加等于1的位置

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

a 0~7
b 0~7
或卷积

c[6] = ?

a[i] * b[j] (i | j) == 6
6是0的位置，i和j必须是0
6是1的位置，i和j至少一个是1

先解决第一个条件，第二个条件用容斥解决

对a和b做子集和变换得到A和B
A[6] = (a[0] + a[2] + a[4] + a[6])
B[6] = (b[0] + b[2] + b[4] + b[6])

A[6] * B[6] = ……16项…… 都满足 6是0的位置，i和j必须是0
其中有一些不满足 6是1的位置，i和j至少一个是1

做子集和变换逆变换

C[6] = A[6] * B[6]

c[6] = C[6] - C[4] - C[2] + C[0]
c[6] = sum(a[i] * b[j]) (i | j) == 6

或卷积
a = 2 4 6 8
b = 1 3 5 7

A = 2 6 8 20
B = 1 4 6 16

C = 2 24 48 320

c = 2 22 46 250


与卷积
a = 2 4 6 8
b = 1 3 5 7

A = 20 12 14 8
B = 16 10 12 7

C = 320 120 168 56

c = 88 64 112 56
  1. 子集和变换
≡