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

题目链接：P4931 [MtOI2018] 情侣？给我烧了！（加强版）

题意：

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

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

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

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

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

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

输入格式：

输入包含多组数据。

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

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

输出格式：

输出共 $T$ 行。

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

数据范围：

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

我看了半天也没看出来这个加强在哪里了，一看讨论区原来是有人原题用暴力卡过去了，有点难绷。

题解的那些高级解法我数学也不好看不懂，以后有机会就来讲高级做法，先放通俗的解法吧。

$\mathcal{Part}\ 1$

记 $g(x)$ 为 $x$ 对情侣都排错的方案数，那么

$f(n,k) =\binom{n}{k}^2\times k! \times 2^k \times g(n-k)$

那么怎么算 $g(x)$ 呢？不妨考虑第一排的三种情况，即两男、两女或一男一女（但不是情侣）

两男：选出两男的方案数为 $x(x-1)$ ，然后考虑他们各自的妹纸在这之后配对的情况
- 强制这两个妹纸配对，那么剩下的 $x-1$ 排中选一排坐且可以互相换座位，方案数为
  $2(x-1)\times g(x-2)$
- 强制这两个妹纸不配对，那么可以把这两个妹纸看作情侣（嗯？），方案数为
  $g(x-1)$
两女：和两男的方案数一样。
一男一女：枚举一男一女，可以交换顺序的方案数为 $2x(x-1)$ ，后面转移其实是一样的。

因此转移方程

$g(x) = 4 x(x-1) \times (g(x-1)+2(x-1) \times g(x-2))$

时间复杂度 $\mathcal{O}(n+T)$

代码：（其实就开大了一下数组然后改了改输出而已……~~甚至都没卡一卡常~~）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))

int pw[N],fac[N],inv[N],g[N];
int qpow(int a,int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
int C(int n, int m)
{
    if(m < 0 || n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void solve()
{
    int n, k; cin >> n >> k;
    cout << C(n,k) * C(n,k) % mod * fac[k] % mod * pw[k] % mod * g[n - k] % mod << '\n';
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fac[0] = pw[0] = 1;
    for(int i = 1; i <= N - 10; i++) pw[i] = pw[i - 1] * 2 % mod;
    for(int i = 1; i <= N - 10; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N - 10] = qpow(fac[N - 10], mod - 2);
    for(int i = N - 10 - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;

    g[0] = 1; g[1] = 0;
    for(int i = 2; i <= 5e6 + 10; i++)
        g[i] = 4 * i * (i - 1) % mod * (g[i - 1] + 2 * (i - 1) * g[i - 2] % mod) % mod;
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}