题解 P4931 【情侣？给我烧了！（加强版）】

给出一个生成函数爆算递推式的方式： 不妨设 $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}$$