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

一共有$n$对情侣。
共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

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

这里关键求出$G(i)$

$$\sum {n\choose k}^2 k!\times 2^kD(n-k) = (2n)!\\ \sum \frac{n!n!}{k!(n-k)!(n-k)!}^2 \times 2^k D(n-k) = (2n)!\\ F(x)=\sum \frac{2^x}{x!},G(x)=\frac{D(x)}{((n-k)!)^2},H(x)=\sum \frac{(2x)!}{(x!)^2}\\ F\times G=H\\ e^{2x}\times G(x)=\sum {2k\choose k} x^k$$

耐心推导：)

$$G(x)=\frac{-e^{2x}}{\sqrt{1-4x}}\\ G^1(x)=\frac{8xe^{-2x}}{(1-4x)^{1.5}}=8xD(x)/(1-4x)\\ G^1(x)=4xD^1(x)+8xD(x),\\(n+1)a_{n}=4n a_n+ 8a_{n-1}$$ $$D(n)=4n(n-1)D(n-1)+8n^2(n-1)D(n-2)$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 5e6 + 10;
const int mod = 998244353;

int qpow(int a, ll x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        x >>= 1;
    }
    return res;
}

int fac[N], facinv[N];
void prepare()
{
    fac[0] = 1;
    facinv[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    facinv[N - 1] = qpow(fac[N - 1], mod - 2, mod);
    for (int i = N - 2; i >= 1; i--)
        facinv[i] = 1ll * facinv[i + 1] * (i + 1) % mod;
}
int C(int n, int i)
{
    if (i == 0)
        return 1;
    if (n <= 0)
        return 0;
    if (i > n)
        return 0;

    return 1ll * fac[n] * facinv[i] % mod * facinv[n - i] % mod;
}

int n, pow2[N], f[N];
int T, ans[N];
int g[N];
int main()
{
    prepare();
    scanf("%d", &T);
    pow2[0] = 1;
    for (int i = 1; i < N; i++)
        pow2[i] = 2ll * pow2[i - 1] % mod;
    g[0] = 1;
    g[1] = 0;
    for (int i = 2; i < N; i++)
        g[i] = 4ll * i * (i - 1) % mod * (g[i - 1] + 2ll * (i - 1) % mod * g[i - 2] % mod) % mod;

    while (T--)
    {
        int k;
        scanf("%d%d", &n, &k);
        f[k] = 1ll * C(n, k) * C(n, k) % mod * pow2[k] % mod * fac[k] % mod;
        f[k] = 1ll * g[n - k] * f[k] % mod;
        printf("%d\n", f[k]);
    }
}