SOSDP高维前缀和

0. 前言

前置知识：

• 状压 DP。

1. 概念与介绍

SOSDP，翻译过来就叫做子集和 DP，又称作高维前缀和，用来解决一些涉及子集和计算的问题。

我们通过一道例题来进行引入：

给你一个含$2^n$ 的集合$S$，对于所有的$i\in [0,2^n-1]$，求解$\sum_{j\subset i}s_j$。

有一个显然的想法是模拟即可$O(4^n)$，但是显然我们可以通过枚举子集轻松做到$O(3^n)$，还能不能可以更优？

上面枚举子集的方法我们看有没有什么问题，我们发现当一个状态的二进制位上有$k$ 个 0，那么它将在其他状态的带的时候被访问$2^k-1$ 次，存在许多重复且无用的计算，原因是因为我们每一个对应的$s_i$ 没有和状态建立起对应的练习，而是直接暴力枚举子集，我们需要添加另一个状态来避免上述的重复计算。

我们考虑状态的设计与添加，设状态$S(sta)=\{ x|x \subset sta\}$。上述的语句其实就是表明这些集合存在许多相交的部分，现在我们需要把这个集合划分为不相交的组。

设状态$S(sta,i)=\{ s|s\subset sta,sta \oplus x< 2^{i+1} \}$。我们将二进制位数从 0 开始从低位向高维表示，那么集合$S(sta,i)$ 表示的就是只有第$i$ 位以及更低位与$sta$ 不同的$x$ 的集合。

我们尝试将$sta$ 与$x$ 建立起来联系，那么有如下的分类讨论：

• $sta$ 第$i$ 位为 0：显而易见的，$sta$ 与$x$ 的第$i$ 位均为 0。因此$x$ 仅有$0\sim i-1$ 位和$sta$ 不同，那么就有$S(sta,i)=S(sta,i-1)$。
• $sta$ 第$i$ 位为 1：
  • 若$x$ 的对应位置为 0，那么就是$S(sta\oplus 2^i,i-1)$。
  • 若$x$ 的对应位置为 1，那么就是$S(sta,i-1)$。

下图描述了如何将$S(sta,i)$ 集合相互关联。任何集合$S(sta,i)$ 的元素都是其子树中的叶子。红色前缀表示的这一部分对其所有子结点都是公共的，而黑色部分允许不同。

实现了这些关系之后，我们可以很容易地写出相应的动态规划。

for(int sta=0;sta<(1<<N);sta++)
{
    dp[sta][-1]=A[sta];// 叶结点
	for(int i=0;i<N;i++)
	{
		if(sta&(1<<i))
			dp[sta][i]=dp[sta][i-1]+dp[sta^(1<<i)][i-1];
		else dp[sta][i]=dp[sta][i-1];
	}
	F[sta]=dp[sta][N-1];
}

注意到空间过于无敌，考虑滚动数组：

for(int i=0;i<(1<<N);i++)
	F[i]=A[i];
for(int i=0;i<N;i++)
	for(int sta=(1<<N)-1;sta>=0;sta--)
	    if(sta&(1<<i))
			F[sta]+=F[sta^(1<<i)];

注意到这里其实可以正序枚举，但是养成好习惯吧以后写倒序的。

时间复杂度为$O(n\cdot 2^n)$。

上面代码所求的是子集和，其实 SOSDP 还可以求超集和。具体的，设数组$f[mask]$ 表示每个集合 mask 的初始值，定义：

$$g[S] = \sum_{T \supseteq S} f[T]$$

我们要求的是所有包含$S$ 的超集的和。

考虑每一位从低到高处理，对于第$i$ 位：

• 如果当前集合 mask 不含第$i$ 位：

  • 就可以加上 含第$i$ 位的集合的贡献（即 mask | (1 << i)）。

这相当于枚举所有包含 mask 的超集。

代码如下：

for(int i=0;i<(1<<n);i++) g[i]=f[i];
for(int i=0;i<n;i++)
    for(int mask=0;mask<(1<<n);mask++)
        if((mask>>i&1)==0)
            g[mask]+=g[mask|(1<<i)];

另一种实现：

for(int i=0;i<N;i++)
	for(int sta=(1<<N)-1;sta>=0;sta--)
	    if(!(sta&(1<<i)))
			F[sta]+=F[sta^(1<<i)];

其实超集和其实相当于就是反过来的子集求和，子集和变化相当于就是从小集合转移到大集合，而超集和变化相当于从大集合转移到小集合。

2.例题

CF165E

SOSDP 模板题。

二进制下与为 0 就是二进制位全部都不一样，那么取反之后就是二进制位完全相同的集合或这个集合的子集即可，通过 SOSDP 即可解决。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=23,MK=2e6+15;
int n,a[MK],f[1<<MN];


int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[a[i]]=a[i];
    }
    for(int i=0;i<22;i++){
        for(int j=0;j<(1<<22);j++){
            if((j>>i&1)&&f[j^(1<<i)]){
                f[j]=f[j^1<<i];
            }
        }
    }
    for(int i=1;i<=n;i++){
        int x=((1<<22)-1)^a[i];
        cout<<(f[x]?f[x]:-1)<<" ";
    }
    return 0;
}

arc100c

考虑$i|j\le k$ 实际上就是两个数在二进制表示下 1 位置的集合为$k$ 表示集合的子集。

注意到我们只需要这个子集的最大值和次大值即可，考虑 SOSDP 维护最大值和次大值的值，转移的时候后合并需要考虑最大值和次大值而变化。答案就是子集的前缀最大值，时间复杂度$O(n\cdot 2^n)$。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=20,INF=1e9;
int n,ans;
pir a[1<<MN];

pir mergep(pir x,pir y){
    pir ret;
    if(x.first<y.first) swap(x,y);
    ret=x;
    if(y.first>ret.second) ret.second=y.first;
    return ret;
}


signed main(){
    cin>>n;
    for(int i=0;i<(1<<n);i++){
        int x;
        cin>>x;
        a[i]=pir(x,-INF);
    }
    for(int i=0;i<n;i++){
        for(int s=0;s<(1<<n);s++){
            if((s>>i)&1){
                a[s]=mergep(a[s],a[s^(1<<i)]);
            }
        }
    }
    for(int i=1;i<(1<<n);i++){
        ans=max(ans,a[i].first+a[i].second);
        cout<<ans<<'\n';
    }
    return 0;
}

CF1208F

有没有感觉这个题和上面的题差不太多，但是这里有了个与操作。但其实不太对，因为上面的问题是限制，这里的问题是求值。

注意到或运算的性质，即只要有一个二进制位为 1 那么这个位数贡献的答案就是定死的，启发我们枚举或的数，这样我们只需要解决后的的与操作了。

考虑如何让答案最大，注意到二进制的与或等操作在每一位都是独立的，启发我们按位贪心，既然是最大，考虑从高位到低位贪心。如果有两个数他们的与在这一位为 1，那么最后的答案中一定有这一位。

我那么我们逐位考虑，并且考虑是否有两个在右边的数他们 “与” 的结果为当前答案的超集即可，有的话答案直接加上这一位。

用 SOSDP 求解即可。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=22;
int n,mn[1<<MN],ans;

struct NodeMX{
    int fir,sec;

    friend NodeMX operator +(const NodeMX &x,const NodeMX &y){
        int xmx=x.fir,ymx=y.fir;
        if(xmx<ymx) swap(xmx,ymx);
        return (NodeMX){xmx,max({ymx,x.sec,y.sec})};
    }
}mx[1<<MN];

signed main(){
    memset(mn,0x3f,sizeof(mn));
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        mx[x]=mx[x]+(NodeMX){i,0};
        mn[x]=min(mn[x],i);
    }
    for(int i=0;i<21;i++){
        for(int j=(1<<21)-1;j>=0;j--){
            if(!(j&(1<<i))){
                mx[j]=mx[j]+mx[j^(1<<i)];
                mn[j]=min(mn[j],mn[j^(1<<i)]);
            }
        }
    }
    for(int i=20;i>=0;i--){
        int now=ans|(1<<i);
        bool flag=0;
        for(int j=now;;j=(j-1)&now){
            if(mn[j]<mx[now^j].sec) flag=1;
            if(flag||!j) break;
        }
        if(flag) ans=now;
    }
    cout<<ans;
    return 0;
}

P6422

注意到$m\le 20$，启发我们进行状压。转化为选若干个数使它们按位或为全集。

设$f(i,S)$ 表示目前到第$i$ 个箱子，至少放了一次玩具构成的集合为$S$ 的方案书，转移枚举选或者不选，显然超时。

考虑优化，注意到我们一开始的只需要让他们按位或Wie全集就可以了，但是按位或如果直接算贡献的话会算重，考虑容斥。

设$f_i$ 表示选取若干个箱子或起来为状态$i$ 的方案数，设$g_i$ 表示选取若干个数火起来为状态$i$ 的子集的方案数。显然，设$cnt_i$ 表示$i$ 有$cnt_i$ 个子集，那么$g_i=2^{cnt_i}$。求解$f_i$ 可以考虑乘上容斥系数即可了，系数见代码即可，时间复杂度$O(n+m\cdot 2^m)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=22,MM=1e6+15,MOD=1e9+7;
int n,m,ans,f[1<<MN],pw2[MM];

void initpw(){
    pw2[0]=1;
    for(int i=1;i<MM;i++){
        pw2[i]=pw2[i-1]*2%MOD;
    }
}

signed main(){
    initpw();
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k,st=(1<<m)-1;
        cin>>k;
        while(k--){
            int x;
            cin>>x;
            st^=(1<<(x-1));
        }
        f[st]++;
    }
    for(int i=0;i<21;i++){
        for(int j=0;j<(1<<21);j++){
            if((j>>i)&1){
                (f[j^(1<<i)]+=f[j])%=MOD;
            }
        }
    }
    for(int i=0;i<(1<<m);i++){
        int cnt=__builtin_popcountll(i);
        if(cnt&1){
            ans=(ans-pw2[f[i]]+MOD)%MOD;
        }
        else ans=(ans+pw2[f[i]])%MOD;
    }
    cout<<ans;
    return 0;
}