SOS DP
高维度数组求前缀和
例如4维数组f[d1][d2][d3][d4]，每个维度分别为d1,d2,d3,d4
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
| int f[d1][d2][d3][d4];
for (int i1=1; i1<d1; i1++) {
for (int i2=1; i2<d2; i2++) {
for (int i3=1; i3<d3; i3++) {
for (int i4=1; i4<d4; i4++) {
f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
}
}
}
}
for (int i1=1; i1<d1; i1++) {
for (int i2=1; i2<d2; i2++) {
for (int i3=1; i3<d3; i3++) {
for (int i4=1; i4<d4; i4++) {
f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
}
}
}
}
for (int i1=1; i1<d1; i1++) {
for (int i2=1; i2<d2; i2++) {
for (int i3=1; i3<d3; i3++) {
for (int i4=1; i4<d4; i4++) {
f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
}
}
}
}
for (int i1=1; i1<d1; i1++) {
for (int i2=1; i2<d2; i2++) {
for (int i3=1; i3<d3; i3++) {
for (int i4=1; i4<d4; i4++) {
f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
}
}
}
}
|
对于有$n$维的数组，第$i$维度为$d_i$，求前缀和其时间复杂度是$\prod \limits_{i=1}^n d_i$
若每个维度大小都相等，$d_i=c$，那么时间复杂度是$c^n$
若$c=2$，这些下标可以用一个$n$位二进制数来表示，二进制数可以代表集合，求前缀和可以认为是求子集和。
求子集和
使用维度大小为2的高维度数组表示子集
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
| int f[2][2][2][2];
for (int i1=1; i1<2; i1++) {
for (int i2=1; i2<2; i2++) {
for (int i3=1; i3<2; i3++) {
for (int i4=1; i4<2; i4++) {
f[i1][i2][i3][i4] += f[i1][i2][i3][i4-1];
}
}
}
}
for (int i1=1; i1<2; i1++) {
for (int i2=1; i2<2; i2++) {
for (int i3=1; i3<2; i3++) {
for (int i4=1; i4<2; i4++) {
f[i1][i2][i3][i4] += f[i1][i2][i3-1][i4];
}
}
}
}
for (int i1=1; i1<2; i1++) {
for (int i2=1; i2<2; i2++) {
for (int i3=1; i3<2; i3++) {
for (int i4=1; i4<2; i4++) {
f[i1][i2][i3][i4] += f[i1][i2-1][i3][i4];
}
}
}
}
for (int i1=1; i1<2; i1++) {
for (int i2=1; i2<2; i2++) {
for (int i3=1; i3<2; i3++) {
for (int i4=1; i4<2; i4++) {
f[i1][i2][i3][i4] += f[i1-1][i2][i3][i4];
}
}
}
}
|
这样非常不elegent，可以利用二进制数的特性，四重for循环可改为枚举二进制数 可以枚举4个二进制位确定是哪个下标累加
1
2
3
4
5
6
| for (int i=0; i<4; i++) {
for (int j=0; j<1<<4; j++) {
int i1=j>>3, i2=j>>2&1, i3=j>>1&1, i4=j&1;
f[i1][i2][i3][i4] += f[i1-(i==0)][i2-(i==1)][i3-(i==2)][i4-(i==3)];
}
}
|
维度大小都是2的高维度数组，用一维数组来表示其实更好处理，只需要将下标看作n位二进制数
对于n个元素的子集，求子集和，时间复杂度$O(n2^n)$
1
2
3
4
5
| for (int i=0; i<n; i++) {
for (int j=0; j<1<<n; j++) {
if (j>>i&1) f[j] += f[j^(1<<i)];
}
}
|
SOS DP
高维度前缀和也称为SOS DP (Sum over Subsets dynamic programming)
以dp视角看待求子集和，$dp_{i,j}$代表只处理了二进制集合$j$的低$i$位的子集和，$dp_{0,i}$对应初始化的$f_i$
状态转移
- $j$的第$i$位为1时, $dp_{i, j} = dp_{i-1, j} + dp_{i-1, j’}$，$j’$代表$j$移除了第i位的1。
- $j$的第$i$位为0时，$dp_{i, j} = dp_{i-1,j}$
时间复杂度是$O(n2^n)$
1
2
3
4
5
6
7
8
9
10
| int dp[n+1][1<<n];
for (int i=1; i<=n; i++) {
for (int j=0; j<1<<n; j++) {
if (j>>(i-1)&1)
dp[i][j] = dp[i-1][j] + dp[i-1][j^(1<<i-1)];
else
dp[i][j] = dp[i-1][j];
}
}
|
例如$n=5$时，
$dp_{3, 10101} = dp_{2, 10101}+dp_{2, 10001} \\= dp_{1, 10101} + dp_{1, 10001} \\= dp_{0, 10101} + dp_{0, 10100} + dp_{0, 10001} + dp_{0, 10000}$
二进制10101末3位的子集分别是10101,10100,10001,10000
由于$dp_{i,j} = dp_{i-1, j}+dp_{i, j’}$，而$j’<j$，使用滚动数组，从小到大枚举2进制状态进行覆盖是安全的。
1
2
3
4
5
| for (int i=0; i<n; i++) {
for (int j=0; j<1<<n; j++) {
if (j>>i&1) f[j] += f[j^(1<<i)];
}
}
|
枚举子集的子集
采用枚举子集的子集的方式计算子集和
时间复杂度是$O(3^n)$
小于$2^n$的非负整数中，含有$k$个$1$的二进制数个数有$\binom{n}{k}$个，其子集有$2^k$个
$\sum \limits_{k=0}^{n} \binom{n}{k}2^k = (1+2)^n$ 二项式展开
1
2
3
4
5
6
| int f[1<<n], sf[1<<n];
for (int i=0; i<1<<n; i++) {
for (int j=i; j!=0; j = (j-1)&i) {
sf[i] += f[j];
}
}
|