自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:05:23，当前版本为作者最后更新于2018-11-05 20:54:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

给出一个生成函数爆算递推式的方式：

不妨设 $D_n$ 是这个问题的“错排”：每对情侣都不在一排的方案数。那么对于答案 $f(n, k)$ 来说就可以用 $D_n$ 进行表示，即考虑坐在一排的情侣是哪几对且他们在哪几排，即

$$f(n,k) = \binom nk^2 D_{n-k} k!2^k$$

这自然而然地导出了恒等式

$$\sum_{k=0}^n \binom nk^2 D_{n-k}k!2^k = (2n)!$$

其中 $\binom nk^2$ 引导我们将生成函数写成

$$f(z) = \sum_{n=0}^\infty \frac{a_n}{n!^2} z^n$$

那么因为

$$\sum_{n=0}^\infty \frac{n!2^n}{n!^2} z^n = \mathrm{e}^{2z} $$$$\sum_{n=0}^\infty \frac{(2n)!}{n!^2}z^n = \frac1{\sqrt{1-4z}} $$

带入原始，我们得到了 $D(z)$ 的生成函数方程

$$D(z) \cdot \mathrm e^{2z} = \frac1{\sqrt{1-4z}}$$

因此

$$D(z) = \frac{\mathrm e^{-2z}}{(1-4z)^{1/2}}$$

这帮助我们得到一个式子用于计算 $D_n$（其实就是容斥）

$$D_n = \sum_{k=0}^n \binom nk^2 (-2)^kk! (2n - 2k)! $$

或者也可以直接卷积，但是这都不够快速。我们考虑对 $D(z)$ 进行求导。

$$D'(z) = \frac{8z\cdot \mathrm e^{-2z}}{(1-4z)^{3/2}} = \frac{8z}{1-4z} D(z) $$

这个微分方程可以帮助我们写出 $D(z)$ 的递推形式了，即

$$D'(z) = 4zD'(z) + 8zD(z)$$

提取系数有

$$D_{n+1} = 4n(n+1)D_n + 8n^2(n+1)D_{n - 1}$$