Re：从零开始的二项式反演

演绎推理是我们在数学中经常遇到的一些方法。对于数列来说，通过原数列计算出新的数列叫作演绎，而通过计算出的数列反推出原数列则被称为反演。

形象化地，如果原数列为 \(g(x)\)，新数列是 \(f(x)\)，且满足：\(\large f(x) = \displaystyle\sum^x_{k = 0}a_{x,k} \times g(k)\)

而反演就是希望我们可以通过 \(f(x)\) 来得到 \(g(x)\)，即 \(\large g(x) = \displaystyle\sum^x_{k = 0}b_{x,k} \times f(k)\)

以上式子经过结合表示为：

\(\large f(x) = \displaystyle\sum^x_{k = 0}a_{x,k} \times g(k) \Rightarrow g(x) = \displaystyle\sum^x_{k = 0}b_{x,k} \times f(k)\)

数列反演有许许多多种不同的类型，就例如莫比乌斯反演，二项式反演等等。其实，我们发现反演其实就是在解方程，一些方程组有算法上固定的、特殊的解，我们对于这些特殊的算法冠以具体的名字，就例如二项式反演。

\(\large \displaystyle\sum^{n}_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left[n = 0\right]\)

首先，当 \(n = 0\) 时，式子显然成立。

当 \(n > 0\) 时，由二项式定理可得：\(\large \displaystyle\sum^n_{k = 0}\left(-1\right)^k\dbinom{n}{k} = \left(1 - \left(-1\right)\right)^n=0\)

证毕。

\(\large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=0}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

首先，我们拿出一个很显然的式子：\(\large g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(k)\)。

这应该不需要说明吧

\(\large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}\left[n - k = 0\right]\dbinom{n}{k}g(n)\)

\(\large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n - k}{i}\dbinom{n}{k}g(k)\)

\(\large = \displaystyle\sum^{n}_{k = 0}\displaystyle\sum^{n - k}_{i = 0}(-1)^i\dbinom{n}{i}\dbinom{n - i}{k}g(k)\)

\(\large = \displaystyle\sum^{n}_{i = 0}(-1)^i\dbinom{n}{i}\displaystyle\sum^{n - i}_{k = 0}\dbinom{n - i}{k}g(k)\)

又 \(\because \large f(n) = \displaystyle\sum^n_{k=0}\dbinom{n}{k}g(k)\)

\(\large \therefore g(n) = \displaystyle\sum^{n}_{i = 0}(-1)^k\dbinom{n}{k}f(n - k)\)

注意此处将原来的 \(i\) 换成了 \(k\)，便于与原式比较。

\(\large \therefore g(n) = \displaystyle\sum^{n}_{k = 0}(-1)^{n - k}\dbinom{n}{k}f(k)\)

由于公式2、3证法与公式基础公式大同小异（都是同样的带入方法，只是求和的下界与上界不同），所以就不用证了吧（逃

\(\large f(n) = \displaystyle\sum^n_{k=m}\dbinom{n}{k}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^n_{k=m}\left(-1\right)^{n - k}\dbinom{n}{k}f(k)\)

\(\large f(n) = \displaystyle\sum^m_{k=n}\dbinom{k}{n}g(k)\)

\(\large \Leftrightarrow g(n) = \displaystyle\sum^m_{k=n}\left(-1\right)^{k - n}\dbinom{k}{n}f(k)\)

给定 \(n\) 个元素，相对应的就有 \(2^n\) 个集合。现在要在这 \(2^n\) 个集合中取出若干集合，使得他们的交集的元素个数为 \(K\)，求取法的方案数。对 \(10^9+7\) 取模。

数据范围：\(n \leq 10^6\)。

定义 \(f(x)\) 表示交集中有 \(x\) 个元素被固定选择，剩余元素随意选择的方案数（不去重），定义 \(g(x)\) 表示交集恰好有 \(x\) 个元素的方案数，则有：

\(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k) = \dbinom{n}{x}\left(2^{2^{n - x}} - 1\right)\)

\(\large g(x) = \displaystyle\sum^n_{k = x}(-1)^{k - x}\dbinom{n}{k}f(k)\)

而答案为 \(g(K)\)。

时间复杂度 \(\Theta\left(n\right)\)。

点击查看代码

有 \(n\) 个糖果和 \(n\) 个药片，将它们两两配对。每个糖果和药片都有能量值。求糖果的能量大于药片的配对恰好比药片的能量大于糖果的配对多 \(k\) 对的方案数。对 \(10^9+7\) 取模。

数据范围：\(n \leq 2 \times 10^3\)。\(0 \leq k \leq n\)。药片和糖果的能量值在 <code>int</code> 范围内，且 \(2n\) 个能量值保证互不相同。

定义 \(f(x)\) 表示保证有 \(x\) 对糖果的能量大于药片的配对后，剩余 \(n - x\) 对糖果和药片随机匹配的方案数（不去重），\(g(x)\) 表示恰好有 \(x\) 对糖果的能量大于药片的配对的方案数，则有：

\(\large f(x) = \displaystyle\sum^n_{k=x}\dbinom{k}{x}g(k)\)

\(\large g(x) = \displaystyle\sum^n_{k=x}\left(-1\right)^{k - x}\dbinom{k}{x}f(k)\)

接下来目标即为求出 \(f(x)\) 的表达式。（其中不含 \(g(x)\)）

显然我们需要 \(DP\)。

首先，我们对糖果和药片按能量值从小到大排序。定义 \(dp_{i,j}\) 表示将第 \(i\) 个糖果配对后，一共有 \(j\) 对糖果的能量大于药片的配对。根据定义，我们可以很快得出 \(\large dp_{i,j} = dp_{i - 1,j} + \left(tot_i - j + 1\right)dp_{i - 1, j - 1}\)，其中 \(tot_i\) 表示能量值比糖果 \(i\) 小的药片数。

所以，\(\large f(x) = dp_{n,x} \cdot \left(n - x\right)!\)，答案为 \(g\left(\dfrac{n+k}{2}\right)\)。

时间复杂度 \(\Theta\left(n^2\right)\)。

小w一共买了 \(n\) 块喜糖，发给了 \(n\) 个人，每个喜糖有一个种类。这时，小w突发奇想，如果这 \(n\) 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

数据范围：\(type_i \leq n \leq 2 \times 10^3\)。

咕咕咕……

称一个 \(1\) ∼ \(n\) 的排列的完美数为有多少个 \(i\) 满足 \(\left|P_i - i\right| = 1\)。

求有多少个长度为 \(n\) 的完美数恰好为 \(m\) 的排列。答案对 \(10^9 + 7\) 取模。

数据范围：\(1 \leq n \leq 1000\)，\(0 \leq m \leq n\)。

定义 \(f(x)\) 表示强制确定 \(x\) 个位置为完美的，剩下 \(n - x\) 个位置随便放的方案数(不去重)，\(g(x)\) 为恰好有 \(x\) 个位置为完美的方案数。则有：

接下来，我们尝试去得到 \(f(x)\)。

定义 \(dp_{i,j,0/1,0/1}\) 表示当前选到了第 \(i\) 位，一共有 \(j\) 个位置是完美的，是否已经选了 \(i\)，是否已经选了 \(i + 1\) 的方案数。

根据定义，我们可以进行分类讨论：

第 \(i\) 位是完美的：

第 \(i\) 位选 \(i - 1\)：

由状态 \(\left(i - 1, j - 1, 0, 0\right)\) 转移到状态 \(\left(i, j, 0, 0\right)\)。

由状态 \(\left(i - 1, j - 1, 0, 1\right)\) 转移到状态 \(\left(i, j, 1, 0\right)\)。

第 \(i\) 位选 \(i + 1\)：

由状态 \(\left(i - 1, j - 1, 0/1, 0\right)\) 转移到状态 \(\left(i, j, 0, 1\right)\)。

由状态 \(\left(i - 1, j - 1, 0/1, 1\right)\) 转移到状态 \(\left(i, j, 1, 1\right)\)。

第 \(i\) 位是不完美的：

由状态 \(\left(i - 1, j, 0/1, 0\right)\) 转移到状态 \(\left(i, j, 0, 0\right)\)。

由状态 \(\left(i - 1, j, 0/1, 1\right)\) 转移到状态 \(\left(i, j, 1, 0\right)\)。

而 \(f(x) = \left(dp_{n, x, 0, 0} + dp_{n, x, 1, 1}\right) \times \left(n - x\right)!\)，由此，我们便可以求出 \(g(x)\)。最终答案为 \(g(m)\)。

注意此时 \(dp_{i,j,0/1,0/1}\) 可以压维成 \(dp_{0/1,,j,0/1,0/1}\)。

时间复杂度 \(\Theta \left(n^2\right)\)。