题目链接：洛谷

大家一起 日 ♂ % EI

设\(D_i\)表示\(k=0\)时的答案。那么
\[ f(n,k)=\binom{n}{k}^2D_{n-k}k!2^k \]
意义是选择\(k\)对情侣，\(k\)对位置，全排列，左右交换，其他\(n-k\)个排。那么
\[ \sum_{k=0}^n\binom{n}{k}^2D_{n-k}k!2^k=(2n)! \]
根据这个\(\binom{n}{k}^2\)，我们定义【“不知道是什么”生成函数】是
\[ F(z)=\sum_{k\ge 0}\frac{f_k}{(k!)^2}z^k \]
那么
\[ \sum_{k\ge 0}\frac{k!2^k}{(k!)^2}z^k=e^{2z} \]

\[ \sum_{k\ge 0}\frac{(2k)!}{(k!)^2}z^k=(1-4z)^{-\frac{1}{2}} \]

（第二个式子用广义二项式定理展开就可以了）

于是这个【“不知道是什么”生成函数】的乘法就是这个【“不知道是什么”数列卷积】
\[ \begin{aligned} D(z)\times e^{2z}&=(1-4z)^{-\frac{1}{2}} \\ D(z)&=\frac{e^{-2z}}{\sqrt{1-4z}} \\ D'(z)&=\frac{-2e^{-2z}\sqrt{1-4z}+2e^{-2z}(1-4z)^{-\frac{1}{2}}}{1-4z} \\ &=\frac{8ze^{-2z}}{(1-4z)^{\frac{3}{2}}} \\ &=\frac{8z}{1-4z}D(z) \\ D'(z)&=4zD'(z)+8zD(x) \end{aligned} \]
所以
\[ D_{n+1}=4n(n+1)D_n+8n^2(n+1)D_{n-1} \]