题解 P4931 【情侣？给我烧了！（加强版）】
Elegia
·
·
题解
给出一个生成函数爆算递推式的方式：
不妨设 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}