前言
校测被数学干碎了，赶紧来补一点容斥和反演的东西，能补多少算多少吧。
特别说明：这一篇学习笔记是组合数学的第二篇。
反演
这是一个听着很高大上，实际不简单（因为wtcl）的东西。
反演的实质
对于形如下面的式子，我们称左右两式互为反演式：
\[f_i=\sum^{i}_{j=1}A_{i,j}g_j\Leftrightarrow g_i=\sum_{j=1}^iB_{i,j}f_j \]然后 \(f\) 和 \(g\) 可以看成只有一行的矩阵（也就是向量），这个式子就可以看成矩阵乘法求逆（解向量）。
子集反演
首先我们需要知道子集反演解决什么样的问题：在恰好是某个集合与至少/至多是此集合之间转换。
如果我们求一个特定的符合要求的集合 \(A\)，设 \(f(S)\) 表示 \(A=S\) 的答案，\(g(S)\) 表示 \(S\subseteq A\) 的答案，我们钦定选择了 \(T\subseteq S\)，就有 \(g(S)=\sum_{T\subseteq S}f(T)\)，反演得到：\(f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)\)。
证明：将两个式子代一下即可，在此不给出详细证明，后面二项式反演会证，可以参考其证法。
二项式反演
二项式反演是最常见的反演之一，下面给出两种形式并证明第一种。
形式一：
\[f(n)=\sum^{n}_{i=m}{n\choose i}g(i)\Leftrightarrow g(n)=\sum^{n}_{i=m}(-1)^{n-i}{n\choose i}f(i) \]形式二：
\[f(n)=\sum^{n}_{i=m}{i\choose m}g(i)\Leftrightarrow g(n)=\sum^{n}_{i=m}(-1)^{i-m}{i\choose m}f(i) \]形式一证明：
\[\begin{aligned} f(n)&=\sum^{n}_{i=m}{n\choose i}g(i)\\ &=\sum^{n}_{i=m}{n\choose i}\sum^{i}_{j=m}(-1)^{i-j}{i\choose j}f(j)\\ &=\sum^{n}_{j=m}f(j)\sum^{n}_{i=j}{n\choose i}{i\choose j}(-1)^{i-j}\\ &=\sum^{n}_{j=m}f(j)\sum^{n}_{i=j}{n\choose j}{n-j\choose i-j}(-1)^{i-j}\\ &=\sum^{n}_{j=m}f(j){n\choose j}\sum^{n}_{i=j}{n-j\choose i-j}(-1)^{i-j}\\ &=\sum^{n}_{j=m}f(j){n\choose j}\sum^{n-j}_{i=0}{n-j\choose i}(-1)^{i}\\ &=\sum^{n}_{j=m}f(j){n\choose j}[n=j]\\ &=f(n) \end{aligned} \]形式二类似。
常见形式
对于求恰好若干个元素满足条件的题目，若不能直接求，可以考虑先转化成钦定有若干个元素满足条件再套上二项式反演。
例题
简要题意
一个有 \(N\) 个元素的集合有 \(2N\) 个不同子集（包含空集），现在要在这 \(2N\) 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 \(K\)，求取法的方案数，答案模 \(10^9+7\)。
数据范围：\(1\le K\le N\le10^6\)。
题解
我们设 \(f(i)\) 表示选出子集大小恰好为 \(i\) 的方案数，然而我们发现这个东西不好转移。但是，如果我们先求出一个限制条件少一点但是比较好求的东西 \(g(i)\) 再去求 \(f(i)\) 就会简单许多（也许。
于是就有 \(g(i)\) 表示钦定 \(i\) 个元素在交集中（其他元素不考虑），这样 \(g(i)\) 就比较好求了，我们可以把 \(g(i)\) 的式子写出来：\(g(i)={n\choose i}(2^{2^{n-i}}-1)\)。为什么呢？首先我们需要从 \(n\) 个元素中选择 \(i\) 个元素，所以有 \(n\choose i\)，然后对于剩下 \(n-i\) 个元素，我们可以列举出可能存在的集合的可能，也就是 \(2^{n-i}\) 种可能，对于这些集合我们可以选可以不选，但是题目要求至少选一个，所以就是一个 \(2^{n-i}\) 元集去掉空集，然后选的元素与不选的元素之间互有影响所以是乘法原理。
然后就是去找 \(f\) 与 \(g\) 的关系了。其实对于 \(g\)，我们还有另一种求法：\(g(i)=\sum^n_{j=i}{j\choose i}f(j)\)。其实就是对于选出子集大小恰为 \(j\) 的方案中再去选出 \(i\) 个，与第一种方法等价。
然后看到后面这坨直接二项式反演就可以得到：
\[f(i)=\sum^n_{j=i}(-1)^{j-i}{j\choose i}{n\choose j}(2^{2^{n-j}}-1) \]然后直接算就行。
简要题意
有两个序列 \({a_i},{b_i}\) 保证所有元素互不相同。你需要重排 \(b\) 序列，使得恰好有 \(k\) 个 \(i\) 满足 \(a_i>b_i\)。
\(0<k\leq n\leq2000\)
题解
因为每一个 \(a,b\) 关系都是相对独立的，所以可以先对 \(A=\{a_i\}\) 排序。
然后就能想到一个 \(dp_{i,j}\) 表示考虑前 \(i\) 对，恰好有 \(j\) 对满足条件，设 \(f_i\) 表示所有数中恰有 \(i\) 对的方案，所以 \(f_i=(n-i)!dp_{n,i}\)，且 \(f_k\) 即为最后答案。然后就做完了！
但是这个东西似乎无法直接转移（（，所以我们需要换一下思路，那么不妨放宽条件，我们重新定义一个 \(dp_{i,j}\) 表示钦定 \(j\) 对满足条件，设 \(g_i\) 表示所有数中钦定有 \(i\) 对的方案，然后稍加讨论就能转移了：
\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt(a_i)-j+1) \]其中 \(cnt(a_i)\) 表示 \(B=\{b_i\}\) 中比 \(a_i\) 小的数的个数，这个似乎可以直接维护。
然后我们可以找找 \(f\) 与 \(g\) 的关系（这不就是二项式反演的组合意义吗），然后因为：
根据二项式反演有：
\[f(k)=\sum\limits_{i=k} ^n{(-1)^{n-i}\dbinom ik(n-i)!dp_{n,i}} \]莫比乌斯反演
对于一些函数，我们无法快速求出其值，但可以快速求出其倍数或约数的值，我们就能通过莫比乌斯反演快速求值。
积性函数
定义：若一个数论函数 \(f(n)\) 满足 \(f(pq)=f(p)\times f(q),\gcd(p,q)=1\)，则称 \(f(n)\) 是一个积性函数。如果 \(\gcd(p,q)=k,k\in Z\)，仍能满足上式则称 \(f(n)\) 为完全积性函数。
性质：若 \(f(n)\) 与 \(g(n)\) 均为积性函数，则下面函数均为积性函数：
- \(h(x)=f(x^p)\)
- \(h(x)=f^p(x)\)
- \(h(x)=f(x)g(x)\)
- \(h(x)=\sum_{d|x}f(d)g(\frac{x}{d})\)
常见积性函数
- 单位函数 \(\epsilon(n)=[n=1]\)。
- 常数函数 \(1(n)=1\)。
- 幂函数 \(id_k(n)=n^k\)，其中 \(id_1(n)\) 简记为 \(id(n)\)。
- 因数个数函数 \(d(n)=\sum_{d|n}1\)。
- 除数函数 \(\sigma_k(n)=\sum_{d|n}d^k\)，其中 \(k=0\) 时就是因数个数函数，\(k=1\) 时为因数和函数，简记为 \(\sigma(n)\)。
- 欧拉函数 \(\varphi(n)=\sum^n_{i=1}[\gcd(i,n)=1]\)。
- 莫比乌斯函数 \(\mu(n)\)。