Luogu P4931 情侣？给我烧了！（加强版）

发表于 | 更新于 | 阅读次数：

题目描述

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

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

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

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

两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，在没有任何限制条件的情况下，每个人任意就坐一共会有 $(2n)!$ 种不同的就坐方案。

输入输出格式

输入格式：

输入包含多组数据。

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

接下来 $T$ 行，每行包含两个非负整数 $n,k$ ，其意义见题目描述。

输出格式：

对于每组输入数据，输出一行，表示对应的就坐方案数。由于结果可能较大，因此输出对 $998244353$ 取模的结果。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5
1 1
2 0
2 2
2333 666
2333333 1000000

输出样例#1：

1
2
3
4
5
2
16
8
798775522
300377435

说明

对于 $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$

题解

这题看上去很难，仔细思考一下的话也不是很复杂。

首先我们要在 $n$ 个情侣中选出 $k$ 对。 $C_n^k$

然后在在 $n$ 排座位中选出 $k$ 排给这 $k$ 对情侣坐。 $k$ 排可以任意排列。 $C_n^k \times k!=A_n^k$

每排的 $2$ 个人可以换位置。 $2^k$

接下来就是最重要的错排部分。

我们令 $f[x]$ 为 $x$ 对情侣不坐在一起的方案数。

很明显第一排 $2$ 个不是情侣的人的坐法是 $2n \times (2n-2)$

接下来我们考虑第一排坐的 $2$ 个人的情侣

  • 坐在一起，也就是在剩下 $n-1$ 排选一排，转换为剩下 $n-2$ 排情侣需要错排的子问题。注意这两个人是可以换着坐的。 $2 \times (n-1) \times f(n-2)$

  • 不坐在一起，也就是可以把他们两个看成一对情侣。转换为剩下 $n-1$ 排需要错排的子问题。 $f[n-1]$

那么我们 $f$ 的公式也就出来了。

$$f[n]=2n \times (2n-2) \times (f[n-1] + 2 \times (n-1) \times f[n-2])$$

于是结合上面的式子，就可以得到：

$$ans=C_n^k \times A_n^k \times 2^k \times f[n-k]$$

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

const int p = 998244353;
const int N = 5e6;

typedef long long ll; 

int T;
ll n, k;
ll fac[N + 5], inv_fac[N + 5];
ll f[N + 5];

ll C(ll n, ll m) // C(n, m) = n! / [(n - m)! * m!] 
{
	if (n < m)
		return 0;
	return fac[n] * inv_fac[n - m] % p * inv_fac[m] % p;
}

ll A(ll n, ll m)
{
	return fac[n] * inv_fac[n - m] % p;
}

ll qpow(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

void pre() // 处理乘法逆元 & 递推f
{
	fac[0] = 1;
	for (register int i = 1; i <= N; i ++)
		fac[i] = fac[i - 1] * i % p;
	inv_fac[0] = inv_fac[1] = 1;
	for (register int i = 2; i <= N; i ++)
		inv_fac[i] = (p - p / i) * inv_fac[p % i] % p;
	for (register int i = 2; i <= N; i ++)
		inv_fac[i] = inv_fac[i] * inv_fac[i - 1] % p; 
	f[0] = 1, f[1] = 0;
	for (register int i = 2; i <= N; i ++)
		f[i] = ((((i - 1) << 1) % p * f[i - 2] % p + f[i - 1]) % p) * 4 % p * i % p * (i - 1) % p;
}

int main()
{
	pre();
	scanf("%d", &T);
	while (T --)
	{
		scanf("%lld%lld", &n, &k);
		ll ans = C(n, k) % p;
		ans = ans * A(n, k) % p;
		ans = ans * qpow((ll)2, k) % p;
		ans = ans * f[n - k] % p;
		printf("%lld\n", ans);
	}
}