专栏文章

记一道 NOIP 模拟赛计数题

NNaCly_Fish绒布球
个人记录参与者 15已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@min0rmc1
此快照首次捕获于
2025/12/01 18:41
3 个月前
此快照最后确认于
2025/12/01 18:41
3 个月前
查看原文
大家好！我是你们的鱼鱼哦。今天呢，有一位同学问了我一道他们 NOIP 模拟赛中的计数题，给大家分享一下（已确认可公开）。随我一起，看看自己的计数能力是否熟练吧！
题意
给定一个 n×mn \times m 的网格，每行和每列上都有一个袋子，而你可以给每个格子上放置不超过 11 个棋子。对于 (i,j)(i,j) 位置的棋子，可以将其放入第 ii 行或第 jj 列的袋子中。
定义一种放置方案的价值为「将所有棋子收入袋子中，且每个袋子都有恰好一个棋子的方案数」。
对于所有每行每列的棋子数都不超过 dd 的棋子放置方案，求其「价值的 kk 次方」之和。答案对 109+710^9+7 取模。
2≤n,m≤30002 \leq n,m \leq 3000，1≤k≤1091 \leq k \leq 10^9，1≤d≤30001 \leq d \leq 3000。

初步转化

对于这种计数题，如果想不到如何直接设计 DP，那就要考虑找性质，或相关的模型转化啦。而回到本题，这种网格图我们正好有经典的二分图建模：
新建一个左部有 nn 个点，右部有 mm 个点的二分图。若原网格中 (i,j)(i,j) 位置有棋子，就连接二分图中左部的 ii 号点，和右部的 jj 号点。
来想一想，能从这个新模型中得到什么呢？
首先，题目中要求每行每列的棋子都不超过 dd 的限制，在新模型中意义明显：每个点的度数都不能超过 dd。容易证明这是等价的。
而对于「把棋子收入袋中」这个操作，我们需要明确：每个棋子在二分图中都对应着一条边。而每个棋子的收纳有两种可能，正好对应了一条边的两种定向。至于「每个袋子都有恰好一个棋子」的条件，就是要求我们定向之后每个点的入度恰好为 11。
现在，我们就得到转化后的题意了：
转化后的题意
定义一个二分图的价值是将其中所有边定向，使得每个点的入度恰好为 11 的方案数。
对于所有左部有 nn 个点，右部有 mm 个点，n+mn+m 条边，且每个点度数不超过 dd 的有标号无向二分图，求其「价值的 kk 次方」之和。

继续分析

经过题意转化，我们可以想到：如果能求出每个连通块的定向方案，将其 kk 次方乘起来就是整个图的价值了。
如果一个连通块只有一个环，那此时它就是基环树。而基环树定向的方案总是只有 22 种：环顺时针和逆时针各一种。环的方向确定后，要让每个点入度为 11 的方案是唯一的。
根据这一点，我们可以确定一个连通块中有多于 11 个环的话，定向的方案数为 00，这种情况不纳入计数；另一方面，每个连通块都至少要有一个环，否则总边数达不到 n+mn+m。

符号化

现在，我们知道每个连通块都是基环树，也就可以考虑建立生成函数来求解啦。
设 fn,mf_{n,m} 是有 nn 个左部点，mm 个右部点，且以左部点为根，根的度数不超过 d−1d-1，而其它点度数不超过 dd 的有根树的数量。类似地再设 gn,mg_{n,m}，只不过是以右部点为根的情况，则我们可以设其生成函数：
F=∑i,jxiyii!j!fi,j , G=∑i,jxiyii!j!gi,jF=\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}
根据定义，我们知道 FF 应该是由一个左部根（xx）上接着不超过 d−1d-1 个 GG 构成的（不要忘记二分图的边不能连接同侧的点！）；对于 GG 亦然。由此可知对应的生成函数方程：
{F=x∑i=0d−1Gi/i!G=y∑i=0d−1Fi/i!\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,GF,G，因为当树根接入基环时，它的度数会增加 22。我们必须要让树根的度数不超过 d−2d-2 才行。所以我们设
F^=x∑i=0d−2Gii! , G^=y∑i=0d−2Fii!\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=12∑i≥2(F^G^)ii=−12F^G^−12ln⁡(1−F^G^)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)
这里除以 22 是因为环无向，没有正反之分。
最后，我们就可以计算答案了。枚举整个二分图中的连通块个数，则答案为：
n!m![xnym]∑i≥02kiHii!=n!m![xnym]exp⁡(2kH)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=2k−1q=2^{k-1}，答案为
n!m![xnym](exp⁡(−F^G^)1−F^G^)qn!m![x^ny^m] \left(\frac{\exp(-\hat F \hat G)}{1-\hat F \hat G}\right)^q
这里出现了复合函数的形式，内层被复合的就是 F^G^\hat F \hat G。因此，答案可以写为
n!m!∑i=0min⁡(n,m)([ui]e−qu(1−u)q)[xn−iym−i](∑j=0d−2Gjj!)i(∑j=0d−2Fjj!)in!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
这里把 F^\hat F 和 G^\hat G 展开来写了，因为保持原样不利于我们继续推导。现在这个形式，我们就可以用多元 Lagrange 反演啦。
多元 Lagrange 反演
设 F,G∈C[[x1,⋯ ,xn]]n\bold F,\bold G \in \mathbb C[[x_1,\cdots,x_n]]^n，以及 h∈C[[x1,⋯ ,xn]]h\in \mathbb C[[x_1,\cdots,x_n]]（多元形式 Laurent 级数存在主元顺序的问题，这里只用到不含负次项的情况），fi,gif_i,g_i 分别为 F,G\bold F,\bold G 在第 ii 维的分量。
若 fi=xigi(F)f_i=x_i g_i(\bold F) 对 1≤i≤n1\leq i\leq n 成立，则对于任意 n∈Zn\bold n \in \mathbb Z^n，有：
[xn]h(F)=[xn]h⋅Gndet⁡([i=j]−xigi∂gi∂xi)[\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)
解析证明可以参考飞雨烟雁的文章。
先设： A(t)=∑i=0d−1tii! , A^(t)=∑i=0d−2tii!A(t)=\sum_{i=0}^{d-1} \frac{t^i}{i!} \ , \ \hat A(t)=\sum_{i=0}^{d-2} \frac{t^i}{i!} （容易发现，A^(t)\hat A(t) 就是 A′(t)A'(t)）
则套用多元 Lagrange 反演可得答案为
n!m!∑i=0min⁡(n,m)([ui]e−qu(1−u)q)[xn−iym−i]A^(y)iA^(x)iA(y)n−iA(x)m−i∣1−yA(y)A^(y)−xA(x)A^(x)1∣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!∑i=0min⁡(n,m)([ui]e−qu(1−u)q)[xn−iym−i]A^(y)iA^(x)iA(y)n−iA(x)m−i(1−xyA(x)A(y)A^(x)A^(y))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,yx,y 系数的计算分离开来。类似于 [xnym]A(x)A(y)=([xn]A(x))([ym]A(y))[x^n y^m]A(x)A(y)=([x^n]A(x))([y^m]A(y))，我们可以把答案表示为
n!m!∑i=0min⁡(n,m)([ui](1−u)e−qu(1−u)q)([xn−i]A^(x)iA(x)m−i)([ym−i]A^(y)iA(y)n−i)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)
整个式子推到这里，我们就能做到 Θ(nlog⁡2n)\Theta(n \log^2 n) 的时间复杂度了。使用 多项式复合函数 用到的 Bostan—Mori 算法即可。
那么，如何做到更快呢？

进一步优化

目前复杂度的瓶颈在于计算（对于 yy 的那部分是对称的，就不再重复写出）：
ci=[xn−i]A^(x)iA(x)m−i=[xn]A(x)m(xA^(x)/A(x))ic_i=[x^{n-i}]\hat A(x)^i A(x)^{m-i}=[x^n]A(x)^m (x \hat A(x)/A(x))^i
如果我们能以低于 Θ(nlog⁡2n)\Theta(n \log^2 n) 的时间复杂度求出 xA^(x)/A(x)x \hat A(x)/A(x) 的复合逆 P(x)P(x)，剩下的就会容易许多。
假设我们已经得知 P(x)P(x)，根据经典方法可知
ci=[xn−i]A(P(x))mP′(x)(xP(x))n+1c_i=[x^{n-i}] A(P(x))^m P'(x) \left(\frac{x}{P(x)} \right)^{n+1}
问题在于 A(P(x))A(P(x)) 并不容易快速计算，设其为 Q(x)Q(x)，则：
Q(x)=∑i=0d−1P(x)ii!Q(x) = \sum_{i=0}^{d-1} \frac{P(x)^i}{i!}
Q′(x)=P′(x)(Q(x)−P(x)d−1(d−1)!)Q'(x)=P'(x) \left( Q(x)-\frac{P(x)^{d-1}}{(d-1)!}\right)
如此就得到了一个关于 Q(x)Q(x) 的一阶线性微分方程，这是可以用 P6613 的牛顿迭代方法以 Θ(nlog⁡n)\Theta(n \log n) 的时间复杂度计算的。
现在我们回过头来看如何计算 P(x)P(x)，根据其定义可知
∑i=0d−2P(x)i+1i!−x∑i=0d−1P(x)ii!=0\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)Q(x) 那样的式子。虽然时间常数极大，但我们确实得到了一个 Θ(nlog⁡n)\Theta(n \log n) 的做法。

后话

「符号化」及其之后的推导显然已经超过了 NOIP 的考查范围，也有大部分超过了 NOI 的考查范围。如果没有什么别的事要做，那这部分确实是一种不错的理性愉悦。
实话来讲，即使不考虑低于 Θ(n2)\Theta(n^2) 的做法，这题作为 NOIP 模拟赛题也有些难了。用此题来对标 NOIP 难度的计数我想是不太合适的。我甚至没有找到更初等的办法（无需生成函数）来做到 Θ(n2)\Theta(n^2) 的时间复杂度。

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...