发现自己数学好菜好菜 =_=
反演
莫比乌斯反演
莫比乌斯函数
\[\mu(n)= \begin{cases} 1 , &n=1 \\ (-1)^r, & n=p_1p_2 … p_r \\ 0 , & else \end{cases}
\]
莫比乌斯反演的一般形式
\[f(n)=\sum_{d|n} g(d) \Leftrightarrow g(n)=\sum_{d|n} \mu(d)f({n \over d})
\]
\[f(n)=\sum_{n|d} g(d) \Leftrightarrow g(n)=\sum_{n|d} \mu(d)f({d \over n})
\]
本质上是在狄拉克雷卷积下，\(\mu\) 的逆元为 \(\epsilon\)
常用的关于 \(\mu\) 的结论
\[\sum_{d|n}\mu(d)=[n=1]
\]
\[\sum_{d|n}\mu(d){n\over d}= \varphi(n) 即 \mu * ID= \varphi
\]
Min-Max 反演
在一些“大小关系”难以比较的题目中，Min-Max 反演扮演重要角色
一般形式：
\[\max(S)_k=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} {|T|-1 \choose k-1} \min(T)
\]
特别地，在 \(k=1\) 时
\[\max(S)=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} \min(T)
\]
此式在期望下也成立(甚至更常用)
\[\mathbb{E}\max(S)=\sum_{\varnothing \ne T \subseteq S} (-1)^{|T|-1} \mathbb{E} \min(T)
\]
当然，交换 \(\max\) 与 \(\min\) 也是成立的
集训队作业 小Z的礼物
二项式反演
基本形式
\[f(n)=\sum_{i=0}^n (-1)^n {n \choose i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^n {n \choose i} f(i)
\]
进一步地，有
\[f(n)=\sum_{i=0}^n {n \choose i} g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} {n \choose i} f(i)
\]
更进一步地，有
\[f(n)=\sum_{i=n}^m {i \choose n} g(i) \Leftrightarrow g(n)=\sum_{i=n}^m (-1)^{i-n} {i \choose n} f(i)
\]
这个式子更为常用，考虑这个式子的组合意义
\(f(n)\) 表示钦定(至少) \(n\) 个 \(n\) 元素，\(g(n)\) 表示恰好 \(n\) 个元素，那么 \(g(i)\) 对 \(f(n)\) 的贡献有 \({i \choose n}g(i)\)，即 \(f(n)=\sum_{i \ge n}{i \choose n}g(i)\)，而上式的 \(m\) 是选择个数的上界
子集反演
设现在的研究对象是集合 \(A\)，设 \(A=S\) 时的答案为 \(f(S)\)，\(S \subseteq A\) 时的答案为 \(g(S)\)，那么有
\[g(S)=\sum_{T \subseteq S} f(T) \Rightarrow f(S)=\sum_{T \subseteq S} (-1)^{|S|-|T|}g(T)
\]
类似地，当 \(A \subseteq S\) 时答案为 \(g(S)\)
\[g(S)=\sum_{S \subseteq T} f(T) \Rightarrow f(S)=\sum_{S \subseteq T} (-1)^{|T|-|S|}g(T)
\]
组合意义就是恰好为这个集合与最多/最少是这个集合之间的转化