526互联

高维前缀和(SOSDP)

发布时间 2023-08-31 20:02:36作者: 徐子洋

模板

求高维矩阵的前缀和

每个位置上存的是原来单点的值。

一维

点击查看代码 
for (int i = 1; i <= n; i++)
    a[i] += a[i - 1];

二维

  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];

  2. 分解法

    分解成多遍一维前缀和

    点击查看代码 
    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]

别看现在好像分解法代码会麻烦，到高维的时候，分解法思维难度又低，时间复杂度又相对较低。

但好像也不快……

三维

  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] + 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];
        }

  2. 分解法

    点击查看代码 
    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\) 就是答案。并且有：

\[f_s=\sum_{s \subseteq t} g_t \]

\[g_s=\sum_{s \subseteq t}(-1)^{|t|-|s|}f_t \]

点击查看代码 
#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\)。发现这样的图中只存在独立的环或者独立的链，于是我们对两种情况分类讨论一下：

    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)\)。

点击查看代码 
#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;
}