P4921 【情侣？给我烧了！】

加强前这道题还是比较友好的

首先我们设\(g_x\)为x对情侣没有一对坐在一起的数量

然后答案就可以表示成：\(C_n^k*A_n^k*2^k*g_{n-k}\)

这里的复杂度是\(O(T*N)\)，貌似不错，所以现在问题变成求\(p_x\)了

第一篇题解是利用这是一个错牌问题，用递推式解决，复杂度为优秀的\(O(N)\)，但是由于询问的复杂度已经是\(O(T*N)\)了，假设我们并不知道这个递推式，我们还能怎么做呢？

考虑暴力容斥：

所有的情况是\((2*x)!\)，然后一对以上情侣数量为\(C_x^1*(2*x-2)!*2*A_x^1\)，意义是：我可以在x对中选取一对，其他的\(x-1\)对是随便做的，然后这对情侣可以交换位置，并且占领\(A_x^1\)排位置

然后两对以上，三对以上也是差不多的，求出来以后直接容斥就好了，所以整体的柿子长成这样：

\[g_x=\sum_{i=0}^x2*(-1)^i*C_x^i*(2*x-2*i)\]

这个式子暴力去算就好了，复杂度\(O(N^2)\)，所以整体复杂度还是\(O(N^2)\)（注意在具体代码中我把组合数拆开了）

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mod 998244353
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define maxn 1005
int pai[maxn << 1], inv[maxn << 1], g[maxn];
il int mul(int a, int b) {
    return 1ll * a * b % mod;
}
il int qpow(int a, int b) {
    int r = 1;
    while(b) {
        if(b & 1) r = mul(a, r);
        a = mul(a, a), b >>= 1;
    }
    return r;
}
il int C(int n, int m) {
    return mul(mul(pai[n], inv[m]), inv[n - m]);
}
il int A(int n, int m) {
    return mul(pai[n], inv[n - m]);
}
il void solve(int x) {
    rep(i, 0, x) printf("%d\n", mul(mul(C(x, i), qpow(2, i)), mul(A(x, i), g[x - i])));
}
il int get(int x) {
    int ans = 0;
    rep(i, 0, x) {
        int x1 = mul(pai[x], inv[i]), x2 = mul(pai[2 * x - 2 * i], inv[x - i]);
        ans = (ans + mul(mul(mul(x1, x2), qpow(-2, i)), A(x, i))) % mod;
    }
    return (ans + mod) % mod;
}
int main() {
    pai[0] = inv[0] = pai[1] = inv[1] = 1, g[0] = 1, g[1] = 0;
    rep(i, 2, 2000) pai[i] = mul(pai[i - 1], i), inv[i] = qpow(pai[i], mod - 2);
    rep(i, 2, 1000) g[i] = get(i);
    int T = read();
    while(T --) solve(read());
    return 0;
}

P4921 【情侣？给我烧了！】

原文：https://www.cnblogs.com/bcoier/p/11774574.html