电影院排座(Couples in Cinema) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;
const int MAXN = 1005;

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<long long> fact(MAXN, 1), inv(MAXN, 1), pw2(MAXN, 1), g(MAXN, 0);
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        pw2[i] = pw2[i - 1] * 2 % MOD;
    }
    inv[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;

    g[0] = 1;
    g[1] = 0;
    for (int m = 2; m < MAXN; ++m) {
        long long term = (g[m - 1] + 2LL * (m - 1) % MOD * g[m - 2]) % MOD;
        g[m] = 4LL * m % MOD * (m - 1) % MOD * term % MOD;
    }

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        for (int k = 0; k <= n; ++k) {
            long long Cnk = fact[n] * inv[k] % MOD * inv[n - k] % MOD;
            long long Ank = fact[n] * inv[n - k] % MOD;
            long long ans = Cnk * Ank % MOD * pw2[k] % MOD * g[n - k] % MOD;
            cout << ans << "\n";
        }
    }
    return 0;
}