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)\)。