反演原理
考虑两个数列 \(f_i\), \(g_i\).
若存在 \(a_{i,j}\), \(b_{i,j}\), 使得
\[ g_n = \sum_{i=0}^n a_{n,i}f_i \tag{1.1}\] 并且\[ f_n = \sum_{i = 0}^n b_{n,i}g_i \tag{1.2}\]则称这两个数列可以相互反演.
推导
设 delta 函数
\[\delta_{i,j}= \begin{cases} 1 & (i = j) \\ 0 & (i \neq j) \end{cases} \]将 \(1.1\) 式代入 \(1.2\) 式:
\[ \begin{aligned} f_n & = \sum_{i=0}^n b_{n,i}g_i \\ &= \sum_{i=0}^n b_{n,i} \sum_{j=0}^i a_{i,j}f_j \\ &= \sum_{i=0}^n f_i \sum_{j=i}^n b_{n,j}a_{j,i} \end{aligned} \] 因此, 可以得到\[ \sum_{j=i}^n b_{n,j}a_{j,i} = \delta_{n,i} \]
不难发现这是 \(a_{i,j}\) 和 \(b_{i,j}\) 可以对 \(f_i\), \(g_i\) 反演的充要条件.
反演的过程, 也可以看做求逆矩阵的过程, 即给定 \(a_{i,j}\), 求 \(b_{i,j}\) .
事实上, 反演并不局限于数列, 类似的思想也可以用于其他函数, 如集合等.
二项式反演
形式
\[ f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i \iff g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i \tag{2.1}\]
这是一个非常对称的式子.更常见的表达是:
\[f_n = \sum_{i=0}^n {n \choose i} g_i \iff g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i \tag{2.2}\]
我们还可以改变下界: 对于给定的 \(a\),
\[f_n = \sum_{i=a}^n {n \choose i} g_i \iff g_n = \sum_{i=a}^n (-1)^{n-i} {n \choose i} f_i \tag{2.3}\]
此时 \(\forall i \in [0,a-1], f_i, g_i\) 无意义 (或者为0).或者改变上界: 对于给定的 \(n\),
\[ f_k=\sum_{i=k}^n {i \choose k} g_i \iff g_k=\sum_{i=k}^n(-1)^{i-k} {i \choose k} f_i \tag{2.4}\]
另外, 二项式反演也可以看做广义容斥原理的另一种表达.
证明
用到了这个式子
\[ {i \choose j} {j \choose k} = {i \choose k} {i-k \choose i-j} \] 容易利用阶乘证明.懒得打公式了
这是 \((2.1)\) 的证明. 对于 \((2.2)\), \((2.3)\), \((2.4)\), 不难发现证明是类似的.
题目
- hdu1465 不容易系列之一
- UVALive7040 Color
- bzoj3622 已经没有什么好害怕的了
这道题补一句:
\(f_i\) 并不是至少 \(i\) 个偏序的方案数, 而是保证 \(i\) 个偏序, 然后其他任选的方案数. 这意味着有\(j\)(\(j > i\)) 个偏序的方案会被算进 \(j \choose i\) 次.
也就是说, 设 \(g_i\) 表示恰好 \(i\) 个偏序的方案数, 有 \(f_k = \sum_{i=k}^n {i \choose k} g_i\). 然后二项式反演即可得出答案.
Stirling 反演
关于斯特林数:
形式
若
\[ g_{n} = \sum_{k = 1}^{n}{n \brace k}f_{k}\] 则\[ f_{n} = \sum_{k=1}^{n}(-1)^{n-k}{n \brace k}g_{k}\]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\), 因此得证.
第二个式子类似.
事实上, 这两个式子也可以通过反演原理直接得到:
这两个式子在期望意义下也是对的: 设 \(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\) 大元素, 则
\[ k^{th}\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]\]