子集反演 & sos dp 学习笔记
子集反演 & sos dp 学习笔记
子集反演
设 \(g(S)\) 表示集合 \(S\) 的答案，\(f(S)\) 为 \(S\) 的子集的答案和。
根据定义：
\[f(S)=\sum_{T\in S} g(T)
\]
子集反演就是：
\[g(S)=\sum _{T\in S}(-1)^{|S|-|T|}f(T)
\]
本质上就是容斥原理，可感性理解，证明略（给你你也记不住）。
于是便可以通过求 \(f\) 得到 \(g\)。
sos dp
对于每个 \(0\le i<2^n\)，求 \(f_i=\sum _{j\in i} a_j\)。
朴素的做法是直接枚举子集，暴力地是 \(O(4^n)\)，初始时 \(f_i=a_i\)。
for(int i=0;i<1<<n;i++)
for(int j=0;j<i;j++)
if((i|j)==i) f[i]+=f[j];
而众所周知，枚举子集可以做到 \(O(3^n)\)，于是
for(int i=1;i<1<<n;i++){
f[i]+=f[0];
for(int j=i;j;j=(j-1)&i)
f[i]+=f[j];
}
然而，引入高维前缀和的思想，每一位都可以看做一个维度，先枚举维度，对每个维度分别求和，可以做到 \(O(n2^n)\)
具体可看 高维前缀和（sos dp）。
for(int j=0;j<n;j++)
for(int i=0;i<(1<<n);i++)
if(i&(1<<j))f[i]=f[i]+f[i^(1<<j)];