背景

有一類問題和子集有關(guān)。
給你一個集合 $S$，令 $T$ 為 $S$ 的超集，也就是 $S$ 所有子集的集合，求 $T$ 中所有元素的和。

暴力1

先預(yù)處理子集的元素和 $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];

時間復(fù)雜度 $O(n^4)$

暴力2

其實(shí)枚舉子集有個小 trick

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

由二項(xiàng)式定理，時間復(fù)雜度為 $O(3^n)$

子集DP

令 $g_{s,i}$ 為狀態(tài)為 $s$，只考慮后 $i$ 位轉(zhuǎn)移的答案。
那么轉(zhuǎn)移就是

$$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}$$
這樣可以做到不重不漏的轉(zhuǎn)移。
推薦一篇blog，非常形象：https://www.cnblogs.com/maple276/p/17975253

可以發(fā)現(xiàn)，這個轉(zhuǎn)移只和上一層有關(guān)，所以第二維是可以省略的。

前綴和（子集向超集轉(zhuǎn)移）

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

后綴和（超集向子集轉(zhuǎn)移）

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$ 等價于 $\stackrel{?}{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();}
}