洛谷P4921 [MtOI2018] 情侣？给我烧了！题解

题目链接：P4921 [MtOI2018] 情侣？给我烧了！

题意：

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

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

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

你的任务是求出当 $k = 0, 1, … , n$ 时，共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

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

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

输入格式：

输入包含多组数据。

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

接下来 $T$ 行，每行包含 $1$ 个正整数 $n(1 \leq n \leq 1000)$。

输出格式：

对于每组输入数据，输出共 $n + 1$ 行，每行包含 $1$ 个整数，分别表示 $k = 0, 1, …, n$ 时满足恰好有 $k$ 对情侣是和睦的就坐方案数。

upd. 好像本题是被暴力卡过去了才有的加强版，难绷。这篇题解只要改一改就可以过加强版了。

记 $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}(Tn)$

代码：

#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)(2e3 + 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; cin >> n;
    for(int k = 0; k <= 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 <= 1e3 + 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;
}