最值反演学习笔记
考虑通过用一个集合的(min)求(max)（或反过来)
我们构造一个与集合元素个数有关的函数(f(|S|))
(kthmax(S)=sumlimits_{Tsubseteq S}f(|T|)min(T))
对于第(i+1)大的元素的贡献，仅当它是集合中最小的元素才会有贡献，我们枚举剩下的元素个数(j)
所以它被计算了(sumlimits_{j=0}^iC_i^jf(j+1))次。
我们构造的函数(f)要满足:
(large sumlimits_{j=0}^iC_i^jf(j+1)=[i+1=k])
令(large g(i)=[i+1=k],h(i)=f(i+1))
则(large sumlimits_{j=0}^iC_j^i h(j)=g(i))
二项式反演得到
(large h(i)=sumlimits_{j=0}^i (-1)^{i-j}C_i^jg(j))
仅当(j=k-1)时(g(j))不为(0)
(large herefore h(i)=(-1)^{i-k+1}C_{i}^{k-1})
(Large herefore 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)=prodlimits_{i=1}^n p_i^{maxlimits_{jsubseteq S}left{ k_{ij} ight}})
(large g(S)=prodlimits_{i=1}^n p_i^{minlimits_{jsubseteq S}left{ k_{ij} ight}})
(large{ herefore} Large f(S)=prodlimits_{i=1}^n p_i^{sumlimits_{Tsubseteq S} (-1)^{|T|-1}minlimits_{jsubseteq T}left{ k_{ij} ight}}=prodlimits_{Tsubseteq S}g(T)^{(-1)^{|T|-1}})