8.16日 集训倒数第\(7\)天
唉，不知不觉间在ssy中学的暑假集训就要结束了，只剩下一周的时间了，然而byn和yzh还有bao学姐\(21\)号就要走了，暑假就要过去了....
今天模拟赛的第二题很有意思，涉及到了许多的数学知识，正好来恶补一下：
浅谈反演原理和二项式反演
首先来说说什么是反演(inversion)，对于一个序列\(\{f_i\}\)来说，如果存在另一个序列\(\{g_i\}\)，使得以下公式成立:
\[g_n = \sum_{i=0}^{n}a_{ni}f_i \]那么反演其实就是利用\(g_0,g_1,g_2,...,gn\)来求出\(f\)序列，也就是把这个柿子变成：
\[f_n = \sum_{i=0}^{n}b_{ni}g_i \]本质上来说，反演其实是一个解线性方程组的过程，但是你观察后发现，这个矩阵实际上是一个三角矩阵，那必然存在着快捷的方法。对于使得这两个反演公式成立的这些系数应该满足什么条件呢？我们现在就来探讨一番！
反演原理
我们来考虑一下上面的那个柿子：
假设对于上面的任意\(0 \le n \le N\)都满足以下柿子：
那么反演过后的柿子就是：
\[f_n = \sum_{i=0}^{n}b_{ni}g_i \]那么我们将\(g_i\)带入就可以得到下面的式子：
\[\begin{aligned} f_n &= \sum_{i=0}^{n}b_{ni}\sum_{j=i}^{n}a_{nj}f_j（1） \\ &=\sum_{i=0}^{n}f_i \sum_{j=i}^{n}a_{nj}b_{nj} （2） \end{aligned} \]这个时候问题出现了，为什么\((1)\)的式子与\((2)\)相等呢？我们画一个矩阵中的正三角来表示：
\[\begin{bmatrix} b_{n0}a_{00}f_0 & & & \\ b_{n1}a_{10}f_0 & b_{n1}a_{11}f_1 & & \\ b_{n2}a_{20}f_0 & b_{n2}a_{21}f_1 & b_{n2}a_{22}f_2 & \\ \vdots & \vdots & \ddots & \\ b_{nn}a_{n0}f_0 & b_{nn}a_{n1}f_1 & \cdots & b_{nn}a_{nn}f_n \\ \end{bmatrix} \]显然，\((1)\)的式子是按照矩阵中的式子一竖列一竖列来计算的，然后加起来；\((2)\)的式子是按照矩阵中的式子一行一行来计算的，然后加起来。由于整体不变，所以\((1) = (2)\)。
反演的应用
接下来我们介绍二项式反演(binomial inversion)，见下面的公式
\[f_n = \sum_{i=0}^{n}(-1)^iC_{n}^{i}g_i \Leftrightarrow g_n = \sum_{i=0}^{n}(-1)^iC_{n}^{i}f_i \]这个是不是不太熟悉？我们介绍他的另一种情况：
\[f_n = \sum_{i=0}^{n}C_{n}^{i}g_i \Leftrightarrow g_n = \sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}f_i \]那么反演我们就先到这里，接下来介绍二项式定理：
这个很简单，就是下面的这个式子：
好了已经了解了这么多的前置芝士接下来我们该做题目了！
二项式反演与二项式定理的综合
给定\(N\)个点，求有标号DAG数量 \(mod 998244353\)，不强制联通。
设\(f_i\)表示\(i\)个点的答案，首先我们钦定\(i\)个入度为\(0\)的点，然后连向其他的点，这样会算重复，为什么呢？看下面这个图：
这个\(3\)点是\(1\)点和\(2\)点两个入度为\(0\)的点所连接的点，可是\(3\)这个点却被计算了两次，这就是我们说的重复。
接下来我们考虑如何避免重复，我们可以换种方法，我们钦定\(h_{i,j}\)表示\(i\)个点中至少选\(j\)个入度为\(0\)的点的总方案数，\(c_{i,j}\)表示\(i\)个点中恰好选\(j\)个入度为\(0\)的点的总方案数,那么有以下公式:
\[h_{i,j} = \sum_{k=i}^{j}C_{k}^{j}c_{i,k} (1) \]解释一下奥：如果我们先不考虑一个图中的不同情况数，那么答案其实就是：
\[h_{i,j} = \sum_{k=i}^{j} c_{i,k} \]为什么要求和呢？还记得我们之前说\(h\)数组和\(c\)数组的定义吗？\(h\)数组是至少，所以对于恰好\(j\)个而言，他还需要补上\(j+1,j+2,...,m\),那么因为求得是总和，所以我们要加上这一部分，那么为什么要加上
\(C_{k}^{j}\)呢?假设我们现在选取了了\(6\)个点，要从中选出\(3\)个，如下图：
在下面这个图中，选择\(4\)个点的话可能性有\(C_{6}^{4}\)种，每次选出\(4\)个都要乘上对应的\(f_4\)，这就构成了一种贡献。
那么对于式子\((1)\)而言，我们可以运用二项式反演导出另一个式子：
\[c_{i,j} = \sum_{k = i}^{j}C_{k}^{j}(-1)^{k-j}h_{i,k} \]那么\(h_{i,j}\)很好求，首先要从\(i\)个点中选择\(j\)个点，那么运用组合数不难发现是\(C_{i}^{j}\)，接下来我们就得到了两个点集，一个拥有\(j\)个节点，另一个拥有\(i-j\)个节点，那么由于这是一个DAG，所以对于\(j\)个节点连向\(i-j\)个节点，他的总方案数就是\(j(i-j)\),由于每条边拥有两种方向，所以也就是\(2^{j(i-j)}\)种可能性。我们计算的是拥有\(j\)个节点的那一个点集，同时我们也要考虑到那个\(i-j\)个点构成的另一个点集，所以答案又要乘上\(f_{i-j}\)。所以\(h_{i,j}\)就等于：
\[h_{i,j} = C_{i}^{j}2^{j(i-j)}f_{i-j} \] 标签：ssy,个点,多项式,sum,我们,反演,二项式,集训,式子 From： https://www.cnblogs.com/grz0306/p/18363880