记一道 NOIP 模拟赛计数题

· · 个人记录

大家好！我是你们的鱼鱼哦。今天呢，有一位同学问了我一道他们 NOIP 模拟赛中的计数题，给大家分享一下（已确认可公开）。随我一起，看看自己的计数能力是否熟练吧！

:::info[题意]{open} 给定一个 n \times m 的网格，每行和每列上都有一个袋子，而你可以给每个格子上放置不超过 1 个棋子。对于 (i,j) 位置的棋子，可以将其放入第 i 行或第 j 列的袋子中。

定义一种放置方案的价值为「将所有棋子收入袋子中，且每个袋子都有恰好一个棋子的方案数」。

对于所有每行每列的棋子数都不超过 d 的棋子放置方案，求其「价值的 k 次方」之和。答案对 10^9+7 取模。

::: ### 初步转化 对于这种计数题，如果想不到如何直接设计 DP，那就要考虑找性质，或相关的模型转化啦。而回到本题，这种网格图我们正好有经典的**二分图建模**： > 新建一个左部有 $n$ 个点，右部有 $m$ 个点的二分图。若原网格中 $(i,j)$ 位置有棋子，就连接二分图中左部的 $i$ 号点，和右部的 $j$ 号点。 来想一想，能从这个新模型中得到什么呢？ 首先，题目中要求每行每列的棋子都不超过 $d$ 的限制，在新模型中意义明显：每个点的度数都不能超过 $d$。容易证明这是等价的。 而对于「把棋子收入袋中」这个操作，我们需要明确：每个棋子在二分图中都对应着一条边。而每个棋子的收纳有两种可能，正好对应了一条边的两种定向。至于「每个袋子都有恰好一个棋子」的条件，就是要求我们定向之后每个点的入度恰好为 $1$。 现在，我们就得到**转化后的题意**了： :::info[转化后的题意]{open} 定义一个二分图的**价值**是将其中所有边定向，使得每个点的入度恰好为 $1$ 的方案数。 对于所有左部有 $n$ 个点，右部有 $m$ 个点，$n+m$ 条边，且每个点度数不超过 $d$ 的有标号无向二分图，求其「**价值**的 $k$ 次方」之和。 ::: ### 继续分析 经过题意转化，我们可以想到：如果能求出每个连通块的定向方案，将其 $k$ 次方乘起来就是整个图的**价值**了。 如果一个连通块只有一个环，那此时它就是基环树。而基环树定向的方案总是只有 $2$ 种：环顺时针和逆时针各一种。环的方向确定后，要让每个点入度为 $1$ 的方案是唯一的。 根据这一点，我们可以确定一个连通块中有多于 $1$ 个环的话，定向的方案数为 $0$，这种情况不纳入计数；另一方面，每个连通块都至少要有一个环，否则总边数达不到 $n+m$。 ### 符号化 现在，我们知道每个连通块都是基环树，也就可以考虑建立生成函数来求解啦。 设 $f_{n,m}$ 是有 $n$ 个左部点，$m$ 个右部点，且以左部点为根，根的度数不超过 $d-1$，而其它点度数不超过 $d$ 的有根树的数量。类似地再设 $g_{n,m}$，只不过是以右部点为根的情况，则我们可以设其生成函数： $$F=\sum_{i,j} \frac{x^i y^i}{i! j!}f_{i,j} \ , \ G=\sum_{i,j} \frac{x^i y^i}{i! j!}g_{i,j}$$ 根据定义，我们知道 $F$ 应该是由一个左部根（$x$）上接着不超过 $d-1$ 个 $G$ 构成的（不要忘记二分图的边不能连接同侧的点！）；对于 $G$ 亦然。由此可知对应的生成函数方程： $$\begin{cases} F= x \sum_{i=0}^{d-1} G^i/i! \\ G = y \sum_{i=0}^{d-1}F^i/i!\end{cases}$$ 但构成基环树的元素可不是 $F,G$，因为当树根接入基环时，它的度数会增加 $2$。我们必须要让树根的度数不超过 $d-2$ 才行。所以我们设 $$\hat F=x\sum_{i=0}^{d-2}\frac{G^i}{i!} \ , \ \hat G = y \sum_{i=0}^{d-2}\frac{F^i}{i!}$$ 然后我们考虑基环树的构造，环上的点也是依次为左、右部点。枚举环长，可以得到： $$H=\frac 12\sum_{i \geq 2} \frac{(\hat F \hat G)^i}{i}=-\frac 12\hat F\hat G-\frac 12\ln(1-\hat F\hat G)$$ 这里除以 $2$ 是因为环无向，没有正反之分。 最后，我们就可以计算答案了。枚举整个二分图中的连通块个数，则答案为： $$n!m![x^ny^m] \sum_{i \geq 0} \frac{2^{ki} H^i}{i!}=n!m![x^ny^m]\exp(2^k H)$$ 但这个式子的复杂度太大了，让我们慢慢优化。 ### 推式子 先设 $q=2^{k-1}$，答案为 $$n!m![x^ny^m] \left(\frac{\exp(-\hat F \hat G)}{1-\hat F \hat G}\right)^q$$ 这里出现了复合函数的形式，内层被复合的就是 $\hat F \hat G$。因此，答案可以写为 $$n!m!\sum_{i = 0}^{\min(n,m)} \left( [u^i] \frac{\text e^{-qu}}{(1-u)^q}\right)[x^{n-i}y^{m-i}]\left( \sum_{j=0}^{d-2}\frac{G^j}{j!}\right)^i \left( \sum_{j=0}^{d-2}\frac{F^j}{j!}\right)^i$$ 这里把 $\hat F$ 和 $\hat G$ 展开来写了，因为保持原样不利于我们继续推导。现在这个形式，我们就可以用**多元 Lagrange 反演**啦。 :::info[多元 Lagrange 反演] 设 $\bold F,\bold G \in \mathbb C[[x_1,\cdots,x_n]]^n$，以及 $h\in \mathbb C[[x_1,\cdots,x_n]]$（多元形式 Laurent 级数存在主元顺序的问题，这里只用到不含负次项的情况），$f_i,g_i$ 分别为 $\bold F,\bold G$ 在第 $i$ 维的分量。 若 $f_i=x_i g_i(\bold F)$ 对 $1\leq i\leq n$ 成立，则对于任意 $\bold n \in \mathbb Z^n$，有： $$[\bold x^{\bold n}] h(\bold F)=[\bold x^{\bold n}] h\cdot \bold G^{\bold n} \det\left( [i=j]-\frac{x_i}{g_i} \frac{\partial g_i}{\partial x_i}\right)$$ 解析证明可以参考[飞雨烟雁的文章](https://www.luogu.com.cn/article/nn4kvg8x)。 ::: 先设： $$A(t)=\sum_{i=0}^{d-1} \frac{t^i}{i!} \ , \ \hat A(t)=\sum_{i=0}^{d-2} \frac{t^i}{i!}$$ （容易发现，$\hat A(t)$ 就是 $A'(t)$） 则套用多元 Lagrange 反演可得答案为 $$n!m!\sum_{i = 0}^{\min(n,m)} \left( [u^i] \frac{\text e^{-qu}}{(1-u)^q}\right)[x^{n-i}y^{m-i}] \hat A(y)^i \hat A(x)^i A(y)^{n-i}A(x)^{m-i}\begin{vmatrix}1 & -\frac{y}{A(y)}\hat A(y) \\ -\frac{x}{A(x)}\hat A(x) & 1\end{vmatrix}$$ 把行列式算出来即为 $$n!m!\sum_{i = 0}^{\min(n,m)} \left( [u^i] \frac{\text e^{-qu}}{(1-u)^q}\right)[x^{n-i}y^{m-i}] \hat A(y)^i \hat A(x)^i A(y)^{n-i}A(x)^{m-i}\left( 1-\frac{xy}{A(x)A(y)}\hat A(x)\hat A(y)\right)$$ 这么一长串看着复杂，其实我们可以考虑将提取 $x,y$ 系数的计算分离开来。类似于 $[x^n y^m]A(x)A(y)=([x^n]A(x))([y^m]A(y))$，我们可以把答案表示为 $$n!m!\sum_{i = 0}^{\min(n,m)} \left( [u^i] (1-u) \frac{\text e^{-qu}}{(1-u)^q}\right)\left([x^{n-i}]\hat A(x)^i A(x)^{m-i}\right)\left([y^{m-i}]\hat A(y)^i A(y)^{n-i}\right)$$ 整个式子推到这里，我们就能做到 $\Theta(n \log^2 n)$ 的时间复杂度了。使用 [多项式复合函数](https://www.luogu.com.cn/problem/P10249) 用到的 Bostan—Mori 算法即可。 那么，如何做到更快呢？ ### 进一步优化 目前复杂度的瓶颈在于计算（对于 $y$ 的那部分是对称的，就不再重复写出）： $$c_i=[x^{n-i}]\hat A(x)^i A(x)^{m-i}=[x^n]A(x)^m (x \hat A(x)/A(x))^i$$ 如果我们能以低于 $\Theta(n \log^2 n)$ 的时间复杂度求出 $x \hat A(x)/A(x)$ 的复合逆 $P(x)$，剩下的就会容易许多。 假设我们已经得知 $P(x)$，根据[经典方法](https://www.luogu.com.cn/article/c65fzqbm)可知 $$c_i=[x^{n-i}] A(P(x))^m P'(x) \left(\frac{x}{P(x)} \right)^{n+1}$$ 问题在于 $A(P(x))$ 并不容易快速计算，设其为 $Q(x)$，则： $$Q(x) = \sum_{i=0}^{d-1} \frac{P(x)^i}{i!}$$ $$Q'(x)=P'(x) \left( Q(x)-\frac{P(x)^{d-1}}{(d-1)!}\right)$$ 如此就得到了一个关于 $Q(x)$ 的一阶线性微分方程，这是可以用 [P6613](https://www.luogu.com.cn/problem/P6613) 的牛顿迭代方法以 $\Theta(n \log n)$ 的时间复杂度计算的。 现在我们回过头来看如何计算 $P(x)$，根据其定义可知 $$\sum_{i=0}^{d-2} \frac{P(x)^{i+1}}{i!}-x \sum_{i=0}^{d-1} \frac{P(x)^i}{i!}=0$$ 同样可以考虑牛顿迭代来解这个方程，在求解的过程中也需要多次计算形如 $Q(x)$ 那样的式子。虽然时间常数极大，但我们确实得到了一个 $\Theta(n \log n)$ 的做法。 ### 后话 「符号化」及其之后的推导显然已经超过了 NOIP 的考查范围，也有大部分超过了 NOI 的考查范围。如果没有什么别的事要做，那这部分确实是一种不错的理性愉悦。 实话来讲，即使不考虑低于 $\Theta(n^2)$ 的做法，这题作为 NOIP 模拟赛题也有些难了。用此题来对标 NOIP 难度的计数我想是不太合适的。我甚至没有找到更初等的办法（无需生成函数）来做到 $\Theta(n^2)$ 的时间复杂度。