P4931 [MtOI2018]情侣
简要题意
给定 \(T\) 个 \((n,k)\) 二元组，求
\[\sum_{t=k}^n(-1)^{t-k}\binom{t}{k}\binom{n}{k}^2k!2^k(2n-2k)!
\]
\(T\le 2\times10^5,k\le n\le 5\times 10^6\)。
题解
\[\begin{align*}
&\sum_{t=k}^n(-1)^{t-k}\binom{t}{k}\binom{n}{k}^2k!2^k(2n-2k)!\\
=&(n!)^22^k\frac{1}{k!}\sum_{i=0}^{n-k}\frac{(-2)^k}{k!}\binom{2((n-k)-x)}{(n-k)-x}\\
=&(n!)^22^k\frac{1}{k!}\sum_{i=0}^{n-k}u(i)v(n-k-i)\\
=&(n!)^22^k\frac{1}{k!}[x^{n-k}](UV)
\end{align*}
\]
其中 \(u(x)=\displaystyle\frac{(-2)^k}{k!},v(x)=\binom{2x}{x}\)，\(U,V\) 是 \(u,v\) 的生成函数，则有
\[U=e^{-2x}\\
V=\frac{1}{\sqrt{1-4x}}
\]
推导见 link。则有
\[F=UV=\frac{e^{-2x}}{\sqrt{1-4x}}\\
F'=\frac{8x}{1-4x}F\\
F'=4xF'+8xF\\
\]
对比系数有
\[[x^n]F'=4[x^n](xF')+8[x^n](xF)\\
f(n+1)=\frac{4nf(n)+8f(n-1)}{n+1}
\]
直接线性递推即可。
\[ans=(n!)^22^k\frac{1}{k!}f(n-k)
\]
预处理 \(O(n)\)，计算 \(O(1)\)。