题解 P4921 【[MtOI2018]情侣？给我烧了！】

· · 题解

设 g(n) 表示 n 对情侣全部错开的方案数

答案很好表示：

ans_k=\dbinom n k\times A_n^k\times 2^k\times g(n-k)

表示从 n 对座位中选出 k 对给和谐的情侣，从 n 对情侣中有序地选出 k 对和谐的情侣放入，每对情侣可以男生坐左面或男生坐右面

那么我们求出 g(i) 即可

我们在第一排放不和谐的两个人，容易发现，由于他们坐一块了，则他们的情侣都无法配对了，所以他们以及他们的情侣是男是女无所谓

分情况

若他们的两个情侣坐在了一起，则我们需要再选出一排安排给他们，方案数为 2(i-2)\times g(i-2)，乘二是考虑两人可以交换位置

若他们的两个情侣没坐在一起，那我们不妨将他们看成一对配对失败的情侣，则方案数为 g(i-1)

从 2i 个人中选出不为情侣的两个人的方案数为：2i(2i-2)=4i(i-1)

则 g(i)=4i(i-1)\times(g(i-1)+2(i-1)\times g(i-2))

//timeuse:20min
const int N = 1010;
ll fac[N],ifac[N],g[N],t[N];
ll C(int n,int m) { return fac[n] * ifac[n - m] % mod * ifac[m] % mod; }
int main()
{
    int n = 1000;
    fac[0] = 1;for(int i = 1;i <= n;i++) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n],mod - 2);for(int i = n;i;i--) ifac[i - 1] = ifac[i] * i % mod;
    t[0] = 1;for(int i = 1;i <= n;i++) t[i] = Mod(t[i - 1] * 2);
    g[0] = 1,g[1] = 0;
    for(int i = 2;i <= n;i++)
        g[i] = 4 * i * (i - 1) % mod * (g[i - 1] + 2 * (i - 1) * g[i - 2] % mod) % mod;
    int T = read();
    while(T--)
    {
        n = read();
        for(int k = 0;k <= n;k++)
            fprint(C(n,k) * C(n,k) % mod * fac[k] % mod * t[k] % mod * g[n - k] % mod);
    }
    return 0;
}