高维前缀和/sosdp 学习笔记

前言

这个东西还挺神秘的，遂写一篇来说道。

高维前缀和一般解决以下问题：

对于所有的 S,0≤S<2nS,0\leq S<2^n，求出 ∑subS⊆Saj\sum_{subS\sube S}a_j

显然，如果对每一个 ii 都单独枚举子集，复杂度为 O(3n)O(3^n)。而使用高维前缀和的复杂度可以到 O(n⋅2n)O(n\cdot 2^n)。

代码如下：

1
2
3
4
5
for(int i=0;i<n;++i){
    for(int S=0;S<(1<<n);++S){
        if(S&(1<<i)) update(S,S^(1<<i));
    }
}

看起来很一头雾水是不是，怎么 ii 还能在外面的循环的？

而且，这个代码神秘的点就是我有两种方法解释它，看到后面就知道了。

正文

第一种方法：集合

显然对于这种东西，我们能想到一个 dp 做法：对于一个 dpSdp_S，将 SS 删除存在的一位变成 S′S'，然后从所有 dpS′dp_{S'} 转移到 dpSdp_S。

很容易发现这样是有错误的，但凡删除两位就被算了两遍（删除的顺序不同）。

但是发现一个 trick，就是如果令删除的点是单向的，那么这样的问题又不会存在了。

所以说我们在最外层限定一个时间，只允许添加“时间”编号的点。这样就能保证单向的了。

改写一下方便理解。可以自己手玩一下是不是这么个道理。

1
2
3
4
5
for(int i=0;i<n;++i){
    for(int S=0;S<(1<<n);++S){
        if((S&(1<<i))==0) update(S^(1<<i),S);
    }
}
第二种方法：前缀和

link

那么这个东西（指sosdp）是怎么牵扯到前缀和的呢？

咱先不管这个。先考虑前缀和是怎么求的。

一般我们求二维前缀和是容斥来求的。不过我们在这里考虑一维一维的求法。

1
2
3
4
5
6
for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j) dp[i][j]+=dp[i-1][j];
}
for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j) dp[i][j]+=dp[i][j-1];
}

证明都会，也容易理解。

同理，三维前缀和如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j){
        for(int k=1;k<=n;++k) dp[i][j][k]+=dp[i-1][j][k];
    }
}
for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j){
        for(int k=1;k<=n;++k) dp[i][j][k]+=dp[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) dp[i][j][k]+=dp[i][j][k-1];
    }
}

那么考虑高维前缀和，其实也是一维一维来处理的。

解释一下这个代码是什么玩意，这里 SS 实际上是一个每一维都只有 0/1 的 nn 维 dp 状态。那么最外层的时间 tt 相当于当前正在考虑第 tt 维。

那么子集这东西也就是每一维 dp 状态都小于 SS 的玩意罢了。就是一样的。

因此求这个问题就用到了“高维前缀和”这一个看似与子集毫不相干的东西了。

例题

ARC100E

给出 2n2^n 个数 a0,a1,a2,…,a2n−1a_0,a_1,a_2,\dots,a_{2^n-1}。

请你对于所有的 1≤k≤2n−11\leq k\leq 2^n-1，求出使得 i  or  j≤ki \;\text{or} \;j\leq k 的最大 ai+aja_i+a_j。

比较板，但是我用的不太一样。

考虑什么样的集合 S=i  or  jS=i \; \text{or} \; j 能 ≤k\leq k，显然将 kk 二进制展开后，从低到高，但凡有一个 11 没有出现在 SS 中，那么后面即便 SS 出现多少个 11 都是无所谓的。

例如 k=10100101000：

1
2
3
4
0xxxxxxxxxx
100xxxxxxxx
101000xxxxx
10100100xxx

我们只需要令 S=S= 上面的值之后再求出其子集内最大值和次大值就可以了。显然可以用 sosdp 预处理出来。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct Maxs{
	ll mx,se;
	Maxs(){}
	Maxs(ll mx,ll se):mx(mx),se(se){}
	inline void print(){
		cout<<'['<<mx<<","<<se<<"]"<<endl;
	}
}s[maxm];//表示x的子集的a max 和 secondmax

inline void update(int x,int y){
	if(s[y].mx>s[x].mx){
		s[x].se=s[x].mx;
		if(s[y].se>s[x].se) s[x].se=s[y].se;
		s[x].mx=s[y].mx;
	}
	else if(s[y].mx>s[x].se){
		s[x].se=s[y].mx;
	}
}

inline int lowbit(int x){return x&(-x);}
void calc_sos(){
	for(int i=0;i<(1<<n);++i){
		s[i]=Maxs(a[i],-inf);
	}
	for(int i=0;i<n;++i){
		for(int S=0;S<(1<<n);++S){
			if(S&(1<<i)){
				update(S,S^(1<<i));
			}
		}
	}
}


inline int highbit(ll x){
	int res=0;
	if(x>>32) res+=32,x>>=32;
	if(x>>16) res+=16,x>>=16;
	if(x>>8) res+=8,x>>=8;
	if(x>>4) res+=4,x>>=4;
	if(x>>2) res+=2,x>>=2;
	if(x>>1) res+=1,x>>=1;
	return res;
}

void solve(){
	for(int k=1;k<(1<<n);++k){
		int K=k,S;
		ll ans=-inf;
		while(K){
			int top=highbit(K);
			//如果本位无，那么可以随便选
			S=k^K^((1<<top)-1);//计算得到S
			ans=max(ans,s[S].mx+s[S].se);
			K^=(1<<top);
		}
		S=k;
		ans=max(ans,s[S].mx+s[S].se);
		printf("%lld\n",ans);
	}
}

int main(){
	input();
	calc_sos();
	solve();
	return 0;
}

CF165E vj

给你 nn 个数 a1∼na_{1\sim n}，需要你对每个 ii 找出一个 jj 使得 ai  and  aj=0a_i \; \text{and} \;a_j=0，没有则输出 -1。

简单题。把单边取反后就是 aj⊆∁aia_j\sube \complement a_i 了。

CF449D vj

小明有 n 个非负整数 a1,a2,…,ana_1,a_2,\dots,a_n。现在，他想从这些数字中选择一个非空子集，使得这个子集中所有数字的按位与（bitwise AND）结果为 00。小明想知道，满足条件的非空子集有多少个。

请帮助小明计算满足条件的非空子集的数量，并输出结果对 1e9+71e9+7 取模后的值。

显然对 aia_i 取反后就是按位或覆盖值域了。

考虑一个 SS，使用数字对 SS 进行覆盖。所有在 SS 子集的都可以参与覆盖。因此结果数是 2underS2^{under_S}

但是能不能覆盖完全就是另一回事了。这个可以使用容斥排除掉没覆盖完全的。

令 dpdp 为 SS 的 11 的个数为 ii 时的情况总数，简易容斥即可。

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
38
39
40
41
int n;
ll a[maxn],b[maxn];//b=tong
void input(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=(~read())&((1<<20)-1);
		++b[a[i]];
	}
}

ll under[maxn];
void calc_sos(){
	for(int i=0;i<(1<<20);++i) under[i]=b[i]%P;
	for(int i=0;i<20;++i){
		for(int S=0;S<(1<<20);++S){
			if(S&(1<<i)) under[S]=(under[S]+under[S^(1<<i)])%P;
		}
	}
}

ll dp[maxn];
void solve(){
	for(int S=0;S<(1<<20);++S){
		ll add=(_2[under[S]]-1)%P;
		int cnt=0;
		for(int i=0;i<20;++i) if(S&(1<<i)) ++cnt;
		dp[cnt]+=add;
		dp[cnt]%=P;
	}
}

int main(){
	input();
	init();
	calc_sos();
	solve();
	ll ans=0;
	for(int i=20,tf=1;i>=0;--i,tf*=-1) ans=(ans+P+tf*dp[i])%P;
	printf("%lld",ans);
	return 0;
}
高维前缀和/sosdp 学习笔记
https://formu1-github.github.io/Hexo-blog/2025/10/27/高维前缀和-sosdp-学习笔记/
作者
Formu1
发布于
2025年10月27日
许可协议