[笔记] 情侣?给我烧了!

一个影院有 $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} $$

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 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();
}

[笔记] 情侣?给我烧了!

https://mivik.gitee.io/2020/note/burn-couples/

作者

Mivik

发布于

2020-12-19

更新于

2022-08-08

许可协议

评论