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

题目背景

本题原版：P4921

有 $n$ 对情侣来到电影院观看电影。在电影院，恰好留有 $n$ 排座位，每排包含 $2$ 个座位，共 $2 n$ 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 $2 n$ 个座位坐满。

如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。

你的任务是求出共有多少种不同的就坐方案满足恰好有 k 对情侣是和睦的。

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 $(2 n)!$ 种不同的就坐方案。

由于结果可能较大，因此输出对 $998244353$ 取模的结果。

输入包含多组数据。

输入的第 $1$ 行包含 $1$ 个正整数 $T$ ，表示数据的组数。

接下来 $T$ 行，每行包含 $2$ 个正整数 $n, k$ 。

输出共 $T$ 行。

对于每组输入数据，输出共 $1$ 行，包含 $1$ 个整数，表示恰好有 $k$ 对情侣和睦的就坐方案数。

5
1 1
2 0
2 2
2333 666
2333333 1000000

对于 $10 %$ 的数据，满足 $1 \leq T \leq 10, 1 \leq n \leq 5$ 。

对于 $40 %$ 的数据，满足 $1 \leq n \leq 3 \times 10^{3}$ 。

对于 $100 %$ 的数据，满足 $1 \leq T \leq 2 \times 10^{5}, 1 \leq n \leq 5 \times 10^{6}, 0 \leq k \leq n$ 。

设 $d_{n}$ 为 $n$ 对情侣中每对情侣都不在同一排的配对方案数（不是组合数学中的错排）。那么对于答案 $f (n, k)$ 有：

f (n, k) = (C_{n}^{k})^{2} k! 2^{k} d_{n - k}

这自然而然地导出了恒等式

\begin{aligned} \sum_{k = 0}^{n} f (n, k) & =\sum_{k = 0}^{n}(C_{n}^{k})^{2}k!2^{k}d_{n - k} \\ =\sum_{k = 0}^{n}\frac{n!^{2} 2^{k} d_{n - k}}{k! (n - k)!^{2}} \\ =(2n)! \end{aligned}

进而有

\sum_{k = 0}^{n} \frac{2^{k}}{k!} \frac{d_{n - k}}{(n - k)!^{2}} = \frac{(2 n)!}{n!^{2}}

发现等号左侧恰好是一个系数卷积的形式，于是有：

\sum_{k = 0}^{n} \frac{2^{k}}{k!} \frac{d_{n - k}}{(n - k)!^{2}} x^{n} = \frac{(2 n)!}{n!^{2}} x^{n}

定义

D (x) = \sum_{n = 0}^{+ \infty} \frac{d_{n}}{n!^{2}} x^{n}

我们知道

\sum_{n = 0}^{\infty} \frac{2^{n}}{n!} x^{n} = e^{2 x}, \sum_{n = 0}^{\infty} \frac{(2 n)!}{n!^{2}} x^{n} = \frac{1}{\sqrt{1 - 4 x}}

带入原始式，我们得到了生成函数 $D (x)$ 的方程

e^{2 x} D (x) = \frac{1}{\sqrt{1 - 4 x}}

因此

D (x) = \frac{e^{- 2 x}}{\sqrt{1 - 4 x}}

这帮助我们得到一个式子用于计算 $d_{n}$ （其实就是容斥）

\begin{aligned} d_{n} & =n!^{2}\sum_{k = 0}^{n}\frac{(- 2)^{k}}{k!}\frac{(2 n - 2 k)!}{(n - k)!^{2}} \\ =\sum_{k = 0}^{n}(C_{n}^{k})^{2}(-2)^{k}k!(2n-2k)! \end{aligned}

至此，我们得到了 $O (n^{2})$ 的组合数学算法或者 $O (n \log n)$ 的卷积算法，但是这都不够快速。

我们考虑对 $D (x)$ 进行求导。

D^{'} (x) = \frac{8 x \cdot e^{- 2 x}}{(1 - 4 x)^{3 / 2}} = \frac{8 x}{1 - 4 x} D (x)

这个微分方程可以帮助我们写出 $D (x)$ 的递推形式了，即

D^{'} (x) = 4 x D^{'} (x) + 8 x D (x)

在生成函数上的开放形式运算，对于 $D (x)$ ，我们有：

D^{'} (x) = \sum_{n = 1}^{+ \infty} \frac{n d_{n}}{n!^{2}} x^{n - 1}

代入 $D (x)$ 和 $D^{'} (x)$ 的开放形式，令等式左右两边关于 $x_{n}$ 的系数相等，有

d_{n + 1} = 4 n (n + 1) d_{n} + 8 n^{2} (n + 1) d_{n - 1}

于是我们得到了线性的递推方程。