for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
分解法
分解成多遍一维前缀和
for (int i = 1; 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 = 1; j <= n; j++)
a[i][j] += a[i - 1][j]
别看现在好像分解法代码会麻烦，到高维的时候，分解法思维难度又低，时间复杂度又相对较低。
但好像也不快……
三维
容斥
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++) {
a[i][j][k] += a[i][j][k - 1] + a[i][j - 1][k] + a[i - 1][j][k];
a[i][j][k] -= a[i][j - 1][k - 1] + a[i - 1][j - 1][k] + a[i - 1][j][k - 1];
a[i][j][k] += a[i - 1][j - 1][k - 1];
}
分解法
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i][j][k - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i - 1][j][k];
我们来分析一下各自的时间复杂度，容斥在数组每一维的范围的大小为 n ，有 k 维的时候他的时间花销是 n^k\times2^k ，然而我们发现分解法是 n^{k+1} ，接下来便一目了然了。
子集DP基础
这类问题中每个状态集合有一个权值，要求每个状态的子集权值和（或者其他）。
我们不难想到可以利用容斥，对每个状态都进行一遍容斥，那样暴力大概是 4^n 次方的；我们再考虑子集枚举，那样是 3^n 的（a_s 为 s 状态的单点值）。
for(int s = 0; s < (1 << n); s++)
for(int t = (s - 1) & s; t; t = (t - 1) & s)
f[s] += a[t];
给个复杂度分析吧，假设当前状态的某一位为 1，那枚举到的子集当前这一位有两种可能：
若为 $0$，那枚举到的只可能是 $0$。共计 $3$ 种情况，但是总共有 $n$ 位，故而利用乘法原理为 $3^n$。
接下来要介绍一种 $2^n \times n$ 的方法，有 $2$ 种不同的理解方法。
#### 方法 $1$：更换枚举顺序法
我们考虑在有重复的做法中更换枚举顺序以确保不重复。
我们原来是怎样呢（有重复，且以下每个位置上存的是原来单点的值）？
```cpp
for (int s = 0; s < (1 << n); s++)
for (int i = 1; i <= n; i++)
if (!(s & (1 << i - 1)))
f[s | (1 << i - 1)] += f[s];
```
这样会出现重复。然后我们把内层循环提出来到外层：
```cpp
for (int i = 1; i <= n; i++)
for (int s = 0; s < (1 << n); s++)
if (!(s & (1 << i - 1)))
f[s | (1 << i - 1)] += f[s];
```
此外填表法也可以：
```cpp
for(int i = 1; i <= n; i++)
for(int s = 0; s < (1 << n); s++)
if(s & (1 << i - 1))
f[s] += f[s ^ (1 << i - 1)];
```
我们思考，这里有必要更换 $s$ 的枚举顺序吗？然而是不用的，因为 $f_{s \bigoplus 2^{i-1}}$ 的当前这一位是 $0$，故而它根本没更新过。
好了，接下来是此做法的证明：
我们考虑子状态 $t$ 会转移到其超集 $s$ 几次，若能保证转移恰好 $1$ 次便能判断无重复也无遗漏。
一个 $t$ 的转移必定是第一次转移到 $t|\text{其位置上为0的最低位}$，以此类推，把其与 $s$ 相差的位置从低到高补上去（即把 $t$ 原来位置上的权值逐渐转以上去），最后加到 $s$ 里，这个过程中无重复，也同样能保证能转移到 $s$。
举个例子（下面使用二进制状态）：
```
t:011101
s:010100
那么只可能是010101转移到t而不可能是011100转移过去
```
#### 方法 $2$：通过 $\text{DP}$ 式的化简去理解
我们定义 $a_s$ 为 $s$ 状态的单点值，$f_{s,i}$ 为 $s$ 的子集中，只有最靠右 $i$ 位允许与 $s$ 不同的子集的和。
有：
* 初始时 $f_{s,0}=a_s$。
* 答案为 $f_{s,n}$。
* 转移：
$$
f_{s,i}=
\begin{cases}
f_{s,i-1} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \text{if} ~ \{i\} \notin s\\
f_{s,i-1} + f_{s - \{i\},i-1} ~~~~~~~~~~~~~~~~~~~~~~~~~ \text{if} ~ \{i\} \notin s
\end{cases}
$$
把第 $2$ 维提到第一维来并把其这一维的空间优化一下，便是上述代码的做法。
再给一遍代码：
```cpp
for(int i = 1; i <= n; i++)
for(int s = 0; s < (1 << n); s++)
if(s & (1 << i - 1))
f[s] += f[s ^ (1 << i - 1)];
```
超集求和也同理：
```cpp
for(int i = 1; i <= n; i++)//刷表法
for(int s = 0; s < (1 << n); s++)
if(s & (1 << i - 1))
f[s ^ (1 << i - 1)] += f[s];
for(int i = 1; i <= n; i++)//填表法
for(int s = 0; s < (1 << n); s++)
if(!(s & (1 << i - 1)))
f[s] += f[s ^ (1 << i - 1)];
```
## 习题
### [[ARC100E] Or Plus Max](https://atcoder.jp/contests/arc100/tasks/arc100_c)
不难发现我们可以处理出每个下标状态的所有子集中 $a_i$ 的最大值和次大值，用一个 `pair<int,int>` 维护，跑一遍 $\text{SOSDP}$，这时每个状态的权值就是最大值加次大值，最终输出的每一个答案都是一个前缀最大值。
```cpp
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = a; i <= b; i++)
#define FR(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
int n, U, ans;
pair<int, int> f[1 << 18];
void upd(pair<int, int> &a, int x){
if(x > a.first) a.second = a.first, a.first = x;
else if(x > a.second) a.second = x;
}
int main(){
scanf("%d", &n), U = (1 << n) - 1;
FL(s, 0, U) scanf("%d", &f[s].first);
FL(i, 1, n) FR(s, U, 1) if(s & (1 << i - 1))
upd(f[s], f[s ^ (1 << i - 1)].first), upd(f[s], f[s ^ (1 << i - 1)].second);
FL(s, 1, U) ans = max(ans, f[s].first + f[s].second), printf("%d\n", ans);
return 0;
}
```
### [CF gym 102412 G](https://codeforces.com/gym/102412/problem/G)
* 给出 $N(1 \leq N \leq 20)$，有 $2^N$ 个物品，标号为 $0$ 到 $2^N-1$。
* 你需要将这些物品染红或者染蓝，代价分别是 $R_i,B_i$($|R_i|,|B_i| \le 10^9$)。
* 要求是所有红色物品以及蓝色物品都对内封闭，求最小代价。
* 封闭的定义：若 $i,j \in S$ 则 $i|j \in S$。
我们不妨先考虑全集染红色还是蓝色。
若染了某一种颜色，那么一定存在一个二进制位 $t(0 \leq t < N)$，包含 $t$ 这位的所有物品都染成这种颜色，不然此方案不成立。
我们发现这个规律可以从全集推广到所有的集合。
故而先用 $\text{SOSDP}$ 关于 $R,B$ 先求出子集和。接着对于当前状态 $s$ 枚举 $t$ 这位，染成一种代价较小的颜色，其余的由已经求好的其它位置转移而来。
核心代码：
```cpp
f[0] = min(R[0], B[0]);
for(int s = 0; s < (1 << n); s++){
f[i] = 1e18;
for(int t = 0; t < n; t++){
if(s & (1 << t)){
int vr = R[s] - R[s ^ (1 << t)];
int vb = B[s] - B[s ^ (1 << t)];
f[s] = min(f[s], f[s ^ (1 << t)] + min(vr, vb));
}
}
}
```
### [CF449D](https://codeforces.com/problemset/problem/449/D)
首先我们让 $c_s$ 表示有多少 $a_i$ 是 $s$ 的超集，那么有：取与后是 $s$ 的超集的集合个数 $f_s=2^{c_i}$（这里把空集也认为是 $s$ 的超集，联系前后文，会发现这样其实不影响计数）。
再让 $g_s$ 表示有多少集合取与后**恰好**是 $s$，那么显而易见 $g_0$ 就是答案。并且有：
$$
f_s=\sum_{s \subseteq t} g_t
$$
$$
g_s=\sum_{s \subseteq t}(-1)^{|t|-|s|}f_t
$$
```cpp
#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, ans, U, a[N], p[N], c[1 << 20];
int main(){
scanf("%d", &n), U = (1 << 20) - 1, p[0] = 1;
L(i, 1, n) scanf("%d", &a[i]), c[a[i]]++, p[i] = p[i - 1] * 2 % mod;
L(i, 1, 20) L(s, 0, U) if(s & (1 << i - 1))
c[s ^ (1 << i - 1)] += c[s], c[s ^ (1 << i - 1)] %= mod;
L(s, 0, U){
if(__builtin_popcount(s) & 1) ans -= p[c[s]], ans %= mod;
else ans += p[c[s]], ans %= mod;
}
printf("%d\n", (ans + mod) % mod);
return 0;
}
```
### [CF383E](https://codeforces.com/problemset/problem/383/E)
拿到这题，看到求答案的方式：“平方的异或和”。这是就能想到可能有两种方式统计答案：
* 直接按照他所说的去算。
算出每一种情况下的数量平方再取个异或和。
* 拆贡献
既然是平方，就无异于点对数，故而可以两两之间统计贡献。
但是这道题拆贡献很难做（或许是没法做），故而考虑直接去算。
我们发现直接统计合法数量很难，故而我们统计不合法数量。我们发现不合法数量必须要求是当前集合补集的子集。我们采用高维前缀和求和即可。
时间复杂度 $O(2^c \times c)$，其中 $c=24$，表示字母数量。
```cpp
#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 1e4 + 10;
int n, U, ans, f[1 << 24];
int main(){
scanf("%d", &n), U = (1 << 24) - 1;
L(i, 1, n){
int s = 0; char ch;
L(j, 1, 3) scanf(" %c", &ch), s |= (1 << ch - 'a');
f[s]++;
}
L(i, 0, 23) L(s, 0, U) if(s & (1 << i))
f[s] += f[s ^ (1 << i)];
L(s, 0, U) ans ^= (n - f[U ^ s]) * (n - f[U ^ s]);
printf("%d\n", ans);
return 0;
}
```
### [[CERC2016] 二分毯 Bipartite Blanket](https://www.luogu.com.cn/problem/P3679)
考虑霍尔定理和广义霍尔定理：
> 霍尔定理：对于一个左部图为 $X$、右部图大小为 $Y$ 的二分图（钦定 $|X|\leq |Y|$），存在边数等于 $|X|$ 的匹配的充要条件是：对于左部图的任何一个点集，右部图中和它相邻的点集大小都大于等于它（相邻的点集指的是所有点出边的并集）。
* 证明：必要条件显然。
可这为什么是充分条件？考虑反证法，如果我们的增广路算法在进行到某一步的时候停止了——令左部图点集为 $X$，右部图点集为 $Y$，$Z$ 是我们能从左部图的非匹配点在增广路图上走到的点。那么 $Y\cap Z$ 内的点都被匹配了。我们会发现 $X\cap Z$ 内的点只能走到 $Y\cap Z$ 内的点，同时 $X\cap Z$ 内有未匹配点，和霍尔定理作为必要条件这一点矛盾了。
* 此外，假设 $|X|>|Y|$，这个定理就不成立了。
> 广义霍尔定理：给定一张二分图。如果存在一个匹配覆盖左部图中的点集 $X$，且存在一个匹配覆盖右部图中的点集 $Y$，那么存在一个匹配同时覆盖 $X$ 和 $Y$。
* 证明：考虑覆盖 $X$ 与覆盖 $Y$ 的两个匹配的异或 $Z$（这里指边集的异或）。根据定义，满足任意一个点的度数都小于等于 $2$。发现这样的图中只存在独立的环或者独立的链，于是我们对两种情况分类讨论一下：
1. 对于一个环
由于当前二分图只有偶环，故而考虑隔一条边取一次。
2. 对于一条链
如果当前是奇链，那就从一端开始隔一条边取一次。
如果当前是偶链，会发现 $X\cup Y$ 不等于两个匹配并集的总点数（注意到 $X,Y$ 与匹配中的点是有区别的，匹配中的点包含了左部点和右部点，而 $X,Y$ 都只是“左部点和右部点”中的一种），于是我们规避掉实际上不处于 $X\cup Y$ 的点就行了。
根据广义霍尔定理，我们对于点集 $A$ 与点集 $B$ 单独考虑合法性，然后再合并方案即可。
* 判定点集 $S$ 的合法性
判断权值是否不小于 $t$ 好做，枚举每个点判断是否在集合里，求和再与 $t$ 比较即可。
判断一个点集是否被至少一个匹配包含，可以依据霍尔定理（要满足下面所述的两个条件）：
1. $|S|$ 不大于 $S$ 的相邻节点集合
2. $S$ 的所有子集满足第 $1$ 条
第 $1$ 条可以直接暴力枚举+统计，第二条采用高维前缀和求解。
* 合并方案
对 $A$ 的所有合法子集按照权值从小到大排序。接着枚举 $B$ 的每个合法子集，$A$ 中能与它组成合法集合 $V$ 的子集必定是排序后的一段后缀（因为当前只需要考虑和 $\geq t$），可以利用双指针解决。
时间复杂度 $O(n2^n+m2^m)$。
```cpp
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
const int N = 22, M = (1 << 20);
int n, m, U, t, t1, t2, a[N], b[N]; ll ans;
int e1[M], e2[M], r1[M], r2[M], w1[M], w2[M], c1[M], c2[M];
void check(int a[], int e[], int w[], int c[]){
FL(s, 0, U){
FL(i, 1, n) if(s & (1 << i - 1))
w[s] += a[i], c[s] |= e[i];
c[s] = (__builtin_popcount(c[s]) >= __builtin_popcount(s));
}
FL(i, 1, n) FL(s, 0, U) if(s & (1 << i - 1))
c[s] = min(c[s], c[s ^ (1 << i - 1)]);
}
int main(){
scanf("%d%d", &n, &m);
FL(i, 1, n) FL(j, 1, m){
char ch; scanf(" %c", &ch);
e1[i] |= (ch - 48 << j - 1);
e2[j] |= (ch - 48 << i - 1);
}
FL(i, 1, n) scanf("%d", &a[i]);
FL(i, 1, m) scanf("%d", &b[i]);
scanf("%d", &t), U = (1 << (n = max(n, m))) - 1;
check(a, e1, w1, c1), check(b, e2, w2, c2);
FL(s, 0, U){
if(c1[s]) r1[++t1] = w1[s];
if(c2[s]) r2[++t2] = w2[s];
}
sort(r1 + 1, r1 + t1 + 1);
sort(r2 + 1, r2 + t2 + 1);
int j = t2 + 1;
FL(i, 1, t1){
while(j > 1 && r2[j - 1] + r1[i] >= t) j--;
ans += t2 - j + 1;
}
printf("%lld\n", ans);
return 0;
}
```