【学习笔记】子集DP

背景

有一类问题和子集有关。
给你一个集合 $S$，令 $T$ 为 $S$ 的超集，也就是 $S$ 所有子集的集合，求 $T$ 中所有元素的和。

暴力1

先预处理子集的元素和 $A_i$，再枚举子集。

for(int s=0; s<(1<<n); s++)
for(int i=0; i<(1<<n); i++)
if(s&i) 
f[s]+=A[i];

时间复杂度 $O(n^4)$

暴力2

其实枚举子集有个小 trick

for(int s=0; s<(1<<n); s++)
for(int i=s; i>0; i=(i-1)&s)
f[s]+=A[i];

由二项式定理，时间复杂度为 $O(3^n)$

子集DP

令 $g_{s,i}$ 为状态为 $s$，只考虑后 $i$ 位转移的答案。
那么转移就是

$$g_{s,i}=\{\begin{array}{ll}{g}_{s,i-1}& s\&(1<<i)=0\\ g_{s,i-1}+g_{s⨁(1<<i),i-1}& otherwise\end{array}$$
这样可以做到不重不漏的转移。
推荐一篇blog，非常形象：https://www.cnblogs.com/maple276/p/17975253

可以发现，这个转移只和上一层有关，所以第二维是可以省略的。

前缀和（子集向超集转移）

for(int i=0; i<n; i++)
{
for(int s=0; s<(1<<n); s++)
{
if(s&_2)
(f[s]+=f[s^_2])%(mod-1);
}
_2<<=1;
}

后缀和（超集向子集转移）

for(int i=0; i<n; i++)
{
for(int s=0; s<(1<<n); s++)
{
if(!(s&_2))
(f[s]+=f[s^_2])%(mod-1);
}
_2<<=1;
}

差分

//后缀差分
for(int i=0; i<20; i++)
{
for(int s=0; s<S; s++)
{
if(!(s&_2))
(f[s]-=f[s^_2])%=mod;
}
_2<<=1;
}

例题

CF165E

定义 $x$ 和 $y$ 相容为 $x\&y=0$，给你一个序列 $A$，对于每个元素，在 $A$ 中找到和它相容的元素。 $|A|\le 10^6,A_i\le 4\times 10^6$

思路

$x\&y=0$ 等价于 $\tilde{x}\&y=y$，那么只需要对$A$做类似前缀和的操作，加法改成覆盖即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int S=1<<22;
void O_o()
{
int n;
cin>>n;
vector<int> f(S,-1),a(n+1);
for(int i=1; i<=n; i++)
{
cin>>a[i];
f[a[i]]=a[i];
}
int _2=1;
for(int i=0; i<=21; i++)
{
for(int s=0; s<S; s++)
{
if(!(s&_2)) continue;
if(f[s^_2]!=-1)
f[s]=f[s^_2];
}
_2<<=1;
}
int t=S-1;
for(int i=1; i<=n; i++)
{
cout<<f[t^a[i]]<<" ";
}
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(2);
int T=1;
//cin>>T;
while(T--)
{
O_o();
}
}

原文地址：https://blog.csdn.net/Eric1561759334/article/details/140672692

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！