//待更qwq
反演原理
二项式反演
若
\[g_i=\sum_{j=1}^i {\binom ij} f_j\]
, 则有
\[ f_i=\sum_{j=1}^i (-1)^{i-j} {i \choose j} g_j \]
同时, 若
\[g_i=\sum_{j=1}^i (-1)^j {i \choose j} f_j\]
, 则有
\[f_i=\sum_{j=1}^i (-1)^j {i \choose j} g_j\]
通过反演原理和组合数的性质不难证明.
0/1? todo
Stirling 反演
Min-Max 容斥
形式
Min-Max 容斥 (最值反演) 是对集合的 \(\min()\) 和 \(\max()\) 函数的容斥.
设 \(S\) 为一个集合, \(min()\) 和 \(max()\) 为集合的最小/最大元素, 那么有
\[\max(S)=\sum_{T \subseteq S}(-1)^{|T|-1}\min(T)\]
\[\min(S)=\sum_{T \subseteq S}(-1)^{|T|-1}\max(T)\]
证明
引理: 在n(n > 0)个数中选奇数个和选偶数个的方案数相同, 即
\[\sum _{i=0}^n (-1)^i \binom{n}{i} = [n = 0]\]
这可以通过对 \(n\) 的奇偶性分类讨论来证明.
对于第一个式子, 只需枚举 \(\min(T)\), 发现除了 \(\max(S)\) 之外的元素系数都为 \(0\), 因此得证.
第二个式子类似.
事实上, 这两个式子也可以通过反演原理直接得到: Min-Max容斥学习笔记 | LNRBHAW
这两个式子在期望意义下也是对的: 设 \(E(x)\) 表示元素 \(x\) 出现的期望操作次数, 那么
\[E(\max(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\min(T))\]
\[E(\min(S))=\sum_{T \subseteq S}(-1)^{|T|-1}E(\max(T))\]
对于一些题而言, 往往把元素的值设为它的出现时间. 那么, \(E(\max(S))\) 就表示 \(S\) 中所有元素都出现的期望操作次数, \(E(\min(S))\) 就表示 \(S\) 中出现任意元素的期望操作次数.
kth Min-Max
上式的推广.
设 \(kth\max (S)\) 表示 \(S\) 的第 \(k\) 大元素, 则
\[ kth\max(S)=\sum_{T \subseteq S} (-1)^{|T|-k} {|T|-1 \choose k-1} \min(T) \]
证明过程与上面类似.
同样, 它在期望意义下也是对的.
题目
hdu4336 Card Collector
hdu4624 Endless Spin
luogu3175 [HAOI2015]按位或
loj2542 「PKUWC 2018」随机游走
luogu4707 重返现世
子集反演
莫比乌斯反演
设数论函数 \(F(x)\), \(f(x)\),
若\(F(n)=\sum_{d|n}f(d)\), 则有
\[ f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d}) \]
若\(F(n)=\sum_{n|d}f(d)\)
\[f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)\]
但是其实更常用的还是这个
\[\sum_{d|n}\mu(d)=[n=1]\]
参考资料
https://www.cnblogs.com/Mr-Spade/p/9636968.html
https://lnrbhaw.github.io/2019/01/05/Min-Max%E5%AE%B9%E6%96%A5%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/
https://www.cnblogs.com/ljq-despair/p/8678855.html
https://www.cnblogs.com/Mr-Spade/p/9638430.html
https://changxv.coding.me/2018/07/10/%E5%90%84%E7%A7%8D%E5%8F%8D%E6%BC%94/
反演魔术：反演原理及二项式反演 – Miskcoo's Space
