【学习笔记】子集DP
背景
有一类问题和子集有关。
给你一个集合 S S S，令 T T T 为 S S S 的超集，也就是 S S S 所有子集的集合，求 T T T 中所有元素的和。
暴力1
先预处理子集的元素和 A i A_i Ai，再枚举子集。
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 ) O(n^4) O(n4)
暴力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 ) O(3^n) O(3n)
子集DP
令 g s , i g_{s,i} gs,i 为状态为 s s s，只考虑后 i i i 位转移的答案。
那么转移就是
g s , i = { g s , i − 1 s & ( 1 < < i ) = 0 g s , i − 1 + g s ⨁ ( 1 < < i ) , i − 1 o t h e r w i s e g_{s,i} = \begin{cases} g_{s,i-1} & s\&(1<<i)=0 \\g_{s,i-1} +g_{s\bigoplus(1<<i),i-1}&otherwise\end{cases} gs,i={gs,i−1gs,i−1+gs⨁(1<<i),i−1s&(1<<i)=0otherwise
这样可以做到不重不漏的转移。
推荐一篇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 x x 和 y y y 相容为 x & y = 0 x\&y=0 x&y=0，给你一个序列 A A A，对于每个元素，在 A A A 中找到和它相容的元素。 ∣ A ∣ ≤ 1 0 6 , A i ≤ 4 × 1 0 6 |A|\leq 10^6,A_i\leq 4\times 10^6 ∣A∣≤106,Ai≤4×106
思路
x & y = 0 x\&y=0 x&y=0 等价于 x ˜ & y = y \~x\&y=y x˜&y=y，那么只需要对 A A 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();}
}