最值反演学习笔记
考虑通过用一个集合的\(min\)求\(max\)（或反过来)
我们构造一个与集合元素个数有关的函数\(f(|S|)\)
\(kthmax(S)=\sum\limits_{T\subseteq S}f(|T|)min(T)\)
对于第\(i+1\)大的元素的贡献，仅当它是集合中最小的元素才会有贡献，我们枚举剩下的元素个数\(j\)
所以它被计算了\(\sum\limits_{j=0}^iC_i^jf(j+1)\)次。
我们构造的函数\(f\)要满足:
\(\large \sum\limits_{j=0}^iC_i^jf(j+1)=[i+1=k]\)
令\(\large g(i)=[i+1=k],h(i)=f(i+1)\)
则\(\large \sum\limits_{j=0}^iC_j^i h(j)=g(i)\)
二项式反演得到
\(\large h(i)=\sum\limits_{j=0}^i (-1)^{i-j}C_i^jg(j)\)
仅当\(j=k-1\)时\(g(j)\)不为\(0\)
\(\large \therefore h(i)=(-1)^{i-k+1}C_{i}^{k-1}\)
\(\Large \therefore f(i)=(-1)^{i-k}C_{i-1}^{k-1}\)
常用的当\(k=1\)时\(f(i)=(-1)^{i-1}\)就是普通的\(min-max\)容斥。
例题
\(gcd-lcm\)反演
已知\(g(S)=gcd(S)\),求\(f(S)=lcm(S)\)
设有\(n\)个质因子，\(p_i\)表示第\(i\)个质因子,\(k_{ij}\)表示集合中第\(i\)个元素的第\(j\)个质因子的指数。
\(\large f(S)=\prod\limits_{i=1}^n p_i^{\max\limits_{j\subseteq S}\left\{ k_{ij}\right\}}\)
\(\large g(S)=\prod\limits_{i=1}^n p_i^{\min\limits_{j\subseteq S}\left\{ k_{ij}\right\}}\)
\(\large{\therefore} \Large f(S)=\prod\limits_{i=1}^n p_i^{\sum\limits_{T\subseteq S} (-1)^{|T|-1}\min\limits_{j\subseteq T}\left\{ k_{ij}\right\}}=\prod\limits_{T\subseteq S}g(T)^{(-1)^{|T|-1}}\)