Luogu P4931

使劲反演、生成函数，数学功底似乎得有比较高的要求。

题意：有 $n$ 对 CP，任意做 $n$ 排双人座，求恰好有 $k$ 对 CP 坐在一排的方案数。$T(T\leq 2\times 10 ^ 5)$ 组数据，$n\in [1, 5\times 10 ^ 6]$，$ k\in [0, n]$。

看到恰好，显然容斥。

这里可以用到二项式反演，具体地，我们考虑 $f(k)$ 表示恰好 $k$ 对 CP 坐在一排，$g(k)$ 表示钦定 $k$ 对 CP 坐在一排。

$g(k)$ 是好求的，显然就是 $\displaystyle \binom nk ^ 2k!2 ^ k(2(n - k))!$，分别是选 CP，选座位，任意排列 CP，CP 位置交换，剩下的人随便坐。

由二项式反演可得：

$$f(k) = \sum_{i = k} (-1) ^ {i - k} \binom ik g(k)$$

直接暴力计算，可以做到 $O(n)$ 的时间复杂度，可以通过未通过加强版。

另外，我们可以先选 $k$ 对，然后用 $h(n)$ 表示没有一对 CP 坐在一起的方案数。

那么答案可以写作：

$$ans = \binom nk ^ 2 k! 2 ^ k h(n - k)$$

前面的可以 $O(\log k)$ 回答，主要是后面的看能不能做到 $O(n)$ 递推。

容易得到 $h(n)$ 的表达式为：

$$h(n) = \sum_{i = 0} ^ n (-1) ^ i \binom ni ^ 2 i! 2 ^ i (2(n - i))!$$

容易化为卷积形式，做到 $O(n\log n)$ 的复杂度：

$$h(n) = n! ^ 2 \sum_{i = 0} ^ n \dfrac{(-2) ^ i}{i!} \dfrac{(2(n - i))!}{(n - i)! ^ 2}$$

就是 $h_1(x) = \sum_{n = 0}\dfrac{(-2) ^ i}{i!}x ^ i, h_2(x) = \sum_{n = 0} \dfrac{(2n)!}{n! ^ 2}x ^ i$ 的卷积。

显然需要 $O(n)$ 递推，考虑求出 $h_1(x) \times h_2(x)$ 的生成函数。

$$\begin{aligned} h_1(x) &= \sum_{i = 0}\dfrac{(-2) ^ i}{i!} x^i = e ^ {-2x}\\ h_2(x) &= \sum_{i = 0}\dfrac{2i!}{i! ^ 2} x ^ i = \sum_{i = 0} \binom{2i}i x ^ i \end{aligned}$$

下面的式子可以化为 $\dfrac1{\sqrt {1 - 4x}}$，这里就不再详细展开。

那么就得到 $h(x) = h_1(x) \times h_2(x) = \dfrac{e ^ {-2x}}{\sqrt{1 - 4x}}$（先不考虑前面的 $n! ^ 2$）

考虑求导，那么就是 $h’(x) = \dfrac{8x\times e ^ {-2x}}{(1-4x) ^ {\frac 32}} = \dfrac{8x}{1 - 4x}h(x)$。

提取两边的 $[x ^ n]$，容易得到：

$$\begin{aligned} [x ^ n]F'(x) - 4[x ^ {n - 1}]F'(x) &= 8[x ^ {n - 1}]F(x)\\ (n + 1)f_{n + 1} - 4nf_n &= 8f_{n - 1} \end{aligned}$$

按照此递推即可，时间复杂度 $O(n + T\log k)$。

void init()
{
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; ++ i) fact[i] = (LL) fact[i - 1] * i % Mod;
	infact[N - 1] = qpow(fact[N - 1]);
	for (int i = N - 2; i; -- i) infact[i] = (LL) infact[i + 1] * (i + 1) % Mod;
	inv[1] = 1;
	for (int i = 2; i < N; ++ i) inv[i] = (LL) (Mod - Mod / i) * inv[Mod % i] % Mod;
	f[0] = 1, f[1] = 0;
	for (int i = 1; i < N - 1; ++ i)
		f[i + 1] = (4LL * i * f[i] + 8LL * f[i - 1]) % Mod * inv[i + 1] % Mod;
}

int C(int n, int m) { return (LL) fact[n] * infact[m] % Mod * infact[n - m] % Mod; }

int main()
{
	init();
	int n, k, T;
	std::cin >> T;
	while (T --)
	{
		scanf("%d %d", &n, &k);
		int res = (LL) qpow(C(n, k), 2) * fact[k] % Mod
			* qpow(2, k) % Mod * f[n - k] % Mod * qpow(fact[n - k], 2) % Mod;
		printf("%d\n", res);
	}
	return 0;
}