[笔记] 情侣？给我烧了！

一个影院有 $n$ 排座位，每一排两个座位。有 $n$ 对情侣看电影，每个人随机坐，问恰好有 $K$ 对情侣坐在同一排的方案数。

$T$ 组询问。$1\le T\le 2\cdot 10^5$，$1\le n\le 5\cdot 10^6$，$0\le K\le n$。

题目链接

---

思路

你首先考虑至少 $i$ 对坐一起方案数为 $g_i$，那么有：
$$
g_i=\binom ni\binom nii!2^i(2n-2i)!
$$
也就是说，我们选出 $i$ 排座位，然后选出 $i$ 对情侣坐进去，同时情侣之间可以任意排列所以有 $i!$，然后一堆情侣之间任意坐有 $2^i$，最后其他人任意坐有 $(2n-2i)!$。

然后恰好 $i$ 对坐一起方案数为 $f_i$，有：

$$ \begin{aligned} f_i&=\sum_{j=i}^n\binom ji(-1)^{j-i}g_j\\ &=\sum_{j=i}^n\binom ji(-1)^{j-i}\binom nj^2 j!2^j(2n-2j)!\\ &=\frac{(n!)^2}{i!}\sum_{j=i}^n\frac{(-1)^{j-i}}{(j-i)!}\frac1{\left((n-j)!\right)^2}2^j(2n-2j)! \end{aligned} $$

然后我们转化：

$$ \begin{aligned} A_i&=\frac{(-1)^i}{i!}\\ B_i&=\frac1{\left((n-i)!\right)^2}2^i(2n-2i)!\\ f_i&=\frac{(n!)^2}{i!}\sum_{j=i}^n A_{j-i}B_j \end{aligned} $$

翻转得到：

$$ \begin{aligned} B'_i&=B_{n-i}=\frac1{(i!)^2}2^{n-i}(2i)!\\ f_i&=\frac{(n!)^2}{i!}\sum_{j=i}^n A_{j-i}B'_{n-j}\\ &=\frac{(n!)^2}{i!}\sum_{j=0}^{n-i}A_j B'_{n-i-j} \end{aligned} $$

后面是个严格卷积，记其为 $C_i$。我们有：

$$ \begin{aligned} f_i&=\frac{(n!)^2}{i!}C_{n-i}\\ C_i&=\sum_{j=0}^i\frac{(-1)^{i-j}}{(i-j)!}\frac1{(j!)^2}2^{n-j}(2j)! \end{aligned} $$

那个 $n-j$ 很烦，我们改一下：

$$ \begin{aligned} f_i&=\frac{(n!)^2}{i!}2^{n-i}C_{n-i}\\ C_i&=\sum_{j=0}^i\frac{(-2)^{i-j}}{(i-j)!}\frac1{(j!)^2}(2j)! \end{aligned} $$

欸然后我们发现 $C_i$ 这个东西可以算，$O(n\log n)$ 啪的一下就算完了，很快啊！不过 $n\le 5\cdot 10^6$ 我们得线性。

我们设出 $C_i$ 的生成函数 $C(x)$，于是我们有：

$$ \begin{aligned} C(x)&=\sum_{i=0}^\infty x^i\sum_{j=0}^i\frac{(-2)^{i-j}}{(i-j)!}\frac1{(j!)^2}(2j)!\\ C(x)&=\left(\sum_{i=0}^\infty\frac{(-2)^i}{i!}x^i\right)\cdot\left(\sum_{i=0}^\infty\frac{(2i)!}{(i!)^2}x^i\right)\\ D(x)&=\sum_{i=0}^\infty\frac{(2i)!}{(i!)^2}x^i\\ \frac{\int D(x)dx}x&=\sum_{i=0}^\infty\frac{(2i)!}{i!(i+1)!}x^i \end{aligned} $$

右边那个是卡特兰数，我们直接套：

$$ \begin{aligned} \int D(x) dx&=\frac{1-\sqrt{1-4x}}2\\ D(x)&=\frac1{\sqrt{1-4x}}\\ C(x)&=\frac{e^{-2x}}{\sqrt{1-4x}} \end{aligned} $$

嗯。现在来搞递推式。

$$ \begin{aligned} C'(x)&=e^{-2x}\cdot\frac{2}{(1-4x)\sqrt{1-4x}}+\frac{-2e^{-2x}}{\sqrt{1-4x}}\\ &=\frac{e^{-2x}\cdot 8x}{\sqrt{1-4x}\cdot (1-4x)}\\ &=C(x)\cdot\frac{8x}{1-4x} \end{aligned} $$

然后就是通用套路：

$$ \begin{aligned} C'_i&=8\sum_{j=0}^{i-1}C_i\cdot 4^{i-1-j}\\ &=(i+1)C_{i+1}\\ C_i&=\frac8i\sum_{j=0}^{i-2}C_i\cdot 4^{i-2-j} \end{aligned} $$

记一下前缀和就可以线性推了。（感觉自己好像推麻烦了（不管（（

代码

// Mivik 2020.12.21
#include <mivik.h>

#include <algorithm>
#include <cassert>
#include <vector>

MI cin;

typedef long long qe;

const int mod = 998244353;

inline qe ksm(qe x, int p = mod - 2) {
	qe ret = 1;
	for (; p; p >>= 1, (x *= x) %= mod) if (p & 1) (ret *= x) %= mod;
	return ret;
}
inline int pro(int x) { return x >= mod? x - mod: x; }
inline int per(int x) { return x < 0? x + mod: x; }

const int $n = 5000005;

int fac[$n], ifac[$n], F[$n], p2[$n];
inline void init(int n) {
	for (int i = fac[0] = ifac[0] = 1; i <= n; ++i) fac[i] = (qe)fac[i - 1] * i % mod;
	ifac[n] = ksm(fac[n]); for (int i = n; i > 1; --i) ifac[i - 1] = (qe)ifac[i] * i % mod;
}
inline void work() {
	const int n(R), K(R);
	cout < (qe)F[n - K] * ifac[K] % mod * fac[n] % mod * fac[n] % mod * p2[K] % mod < endl;
}
int main() {
	const int N = 5000000; init(N);
	for (int i = F[0] = p2[0] = 1, cur = 0; i <= N; ++i) {
		p2[i] = pro(p2[i - 1] << 1);
		F[i] = (qe)pro(pro(pro(cur << 1) << 1) << 1) * ifac[i] % mod * fac[i - 1] % mod;
		cur = pro(pro(pro(cur << 1) << 1) + F[i - 1]);
	}
	for (int T = R; T; --T) work();
}