高维前缀和(SOSDP)
模板
求高维矩阵的前缀和
每个位置上存的是原来单点的值。
一维
点击查看代码
for (int i = 1; i <= n; i++)
a[i] += a[i - 1];
二维
-
容斥
点击查看代码
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*2^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\) 或 \(1\)。
若为 \(0\)，那枚举到的只可能是 \(0\)。共计 \(3\) 种情况，但是总共有 \(n\) 位，故而利用乘法原理为 \(3^n\)。
接下来要介绍一种 \(2^n \times n\) 的方法，有 \(2\) 种不同的理解方法。
方法 \(1\)：更换枚举顺序法
我们考虑在有重复的做法中更换枚举顺序以确保不重复。
我们原来是怎样呢（有重复，且以下每个位置上存的是原来单点的值）？
点击查看代码
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];
这样会出现重复。然后我们把内层循环提出来到外层：
点击查看代码
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)];
我们思考，这里有必要更换 \(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\) 维提到第一维来并把其这一维的空间优化一下，便是上述代码的做法。
再给一遍代码：
点击查看代码
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)];
超集求和也同理：
点击查看代码
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
不难发现我们可以处理出每个状态所有子集中 \(a_i\) 的最大值和次大值，用一个 pair<int,int> 维护，跑一遍 \(\text{SOSDP}\)，这时每个状态的权值就是最大值加次大值，最终输出的每一个答案都是一个前缀最大值。
点击查看代码
#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
- 给出 \(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\) 这位，染成一种代价较小的颜色，其余的由已经求好的其它位置转移而来。
核心代码：
点击查看代码
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
首先我们让 \(c_s\) 表示有多少 \(a_i\) 是 \(s\) 的超集，那么有：取与后是 \(s\) 的超集的集合个数 \(f_s=2^{c_i}\)。
再让 \(g_s\) 表示有多少集合取与后恰好是 \(s\)，那么显而易见 \(g_0\) 就是答案。并且有：
点击查看代码
#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
拿到这题，看到求答案的方式：“平方的异或和”。这是就能想到可能有两种方式统计答案：
-
直接按照他所说的去算。
算出每一种情况下的数量平方再取个异或和。
-
拆贡献
既然是平方，就无异于点对数，故而可以两两之间统计贡献。
但是这道题拆贡献很难做（或许是没法做），故而考虑直接去算。
我们发现直接统计合法数量很难，故而我们统计不合法数量。我们发现不合法数量必须要求是当前集合补集的子集。我们采用高维前缀和求和即可。
时间复杂度 \(O(2^c \times c)\)，其中 \(c=24\)，表示字母数量。
点击查看代码
#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
考虑霍尔定理和广义霍尔定理：
霍尔定理：对于一个左部图为 \(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\)。发现这样的图中只存在独立的环或者独立的链，于是我们对两种情况分类讨论一下：
-
对于一个环
由于当前二分图只有偶环，故而考虑隔一条边取一次。
-
对于一条链
如果当前是奇链，那就从一端开始隔一条边取一次。
如果当前是偶链，会发现 \(X\cup Y\) 不等于两个匹配并集的总点数（注意到 \(X,Y\) 与匹配中的点是有区别的，匹配中的点包含了左部点和右部点，而 \(X,Y\) 都只是“左部点和右部点”中的一种），于是我们规避掉实际上不处于 \(X\cup Y\) 的点就行了。
-
根据广义霍尔定理，我们对于点集 \(A\) 与点集 \(B\) 单独考虑合法性，然后再合并方案即可。
-
判定点集 \(S\) 的合法性
判断权值是否不小于 \(t\) 好做，枚举每个点判断是否在集合里，求和再与 \(t\) 比较即可。
判断一个点集是否被至少一个匹配包含，可以依据霍尔定理（要满足下面所述的两个条件）：
- \(|S|\) 不大于 \(S\) 的相邻节点集合
- \(S\) 的所有子集满足第 \(1\) 条
第 \(1\) 条可以直接暴力枚举+统计，第二条采用高维前缀和求解。
-
合并方案
对 \(A\) 的所有合法子集按照权值从小到大排序。接着枚举 \(B\) 的每个合法子集，\(A\) 中能与它组成合法集合 \(V\) 的子集必定是排序后的一段后缀（因为当前只需要考虑和 \(\geq t\)），可以利用双指针解决。
时间复杂度 \(O(n2^n+m2^m)\)。
点击查看代码
#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;
}