P4931 [MtOI2018] 情侣？给我烧了！（加强版）

zhouyuhang / 2023-08-13 / 原文

记 \(f_n\) 为 \(k=0\) 的答案。则有答案为 \(\binom n k ^2 2^k k! f_{n-k}\)。接下来的问题变为怎样对每个 \(n,k\) 求出 \(f_{n-k}\)。

组合意义

以下记 \(\overline{A}\) 为 \(A\) 的情侣。

欲求 \(f_n\)，不妨设第一排坐的两个人是 \(A,B\)，则根据定义有 \(\overline{A}\neq B,\overline{B}\neq A\)。因此，我们考虑 \(\overline{A},\overline{B}\) 坐的位置。

\(\overline{A},\overline{B}\) 坐在同一排。
那么剩下的人的坐法就是 \(f_{n-2}\)。而 \(\overline{A},\overline{B}\) 所在的排和两人的顺序有 \(2(n-1)\) 种可能。从而有这一情况的贡献为 \(2(n-1)f_{n-2}\)。
\(\overline{A},\overline{B}\) 不在同一排。
我们将 \(\overline{A},\overline{B}\) 视为一对情侣，不难发现由于两人被强制不坐在同一排，答案恰为 \(f_{n-1}\)。

而最初合法的 \((A,B)\) 共有 \(4n^2-4n\) 种，从而有递推式 \(f_n=(4n^2-4n)(f_{n-1}+2(n-1)f_{n-2})\)。

生成函数

这里使用 qwaszx 的做法。

我们对 \(f\) 进行二项式反演。显然钦定 \(k\) 对情侣的答案为 \({\binom n k}^2k!2^k(2n-2k)!\)。于是有

\[\begin{aligned} & f_n =\sum_{i=0}^n(-1)^i{\binom n i}^2i!2^i(2n-2i)!\\ & =n!^2\sum_{i=0}^n(-2)^i\frac{(2n-2i)!}{(n-i)!^2i!} \\ & =n!^2\sum_{i=0}^n(-2)^i\binom {2n-2i} {n-i} \frac{1}{i!} \end{aligned} \]

记 \(g_n=\sum_{i=0}^n(-2)^i\binom {2n-2i} {n-i} \frac{1}{i!}\)。则有

\[\begin{aligned} & g_n=[x^n]\left(\sum_{i=0}\frac{(-2)^i}{i!}x^i\right)\left(\sum_{i=0}\binom {2i} i x^i\right) \\ \end{aligned} \]

显然 \(\left(\sum_{i=0}\frac{(-2)^i}{i!}x^i\right)=e^{-2x}\)。现在只需求出 \(\left(\sum_{i=0}\binom {2i} i x^i\right)\) 的封闭形式。注意到 \(\binom {2i} i = \frac{2^i(2i-1)!(2i-3)!\cdots 1!}{i!}=\binom {i-\frac{1}{2}}{i}4^i\)。从而 \(\left(\sum_{i=0}\binom {i-\frac{1}{2}}{i}(4x)^i\right)=(1-4x)^{-1/2}\)。于是 \(g_n=[x^n]e^{-2x}(1-4x)^{-1/2}\)。

记 \(G(x)=e^{-2x}(1-4x)^{-1/2}\)。求导得 \(G'(x)=-2e^{-2x}(1-4x)^{-1/2}+2e^{-2x}(1-4x)^{-3/2}=8xe^{-2x}(1-4x)^{-3/2}=\frac{8x}{1-4x}G(x)\)。移项即有 \((1-4x)G'(x)=8xG(x)\)，展开后有 \((n+1)g_{n+1}-4ng_n=8g_{n-1}\)，即 \(g_{n+1}=\frac{1}{n+1}(4ng_n+8g_{n-1})\)。

复杂度均为 \(\Theta(n)\)。