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

题意：

有 $n$ 对情侣，电影院有 $n$ 排共 $2n$ 个座位，每排 $2$ 个座位，求恰好 $k$ 对情侣坐在同一排的方案数。

$1\le T\le 2\times 10^5,1\le n\le 5\times 10^6,0\le k\le n$。

情侣？给我烧了！

考虑暴力反演。设 $f_k$ 为恰好 $k$ 对在同一排的方案数，$g_k$ 为钦定 $k$ 对在同一排的方案数，有：

$$ g_k=\sum_{i=k}^n \binom{i}{k}f_i=\binom{n}{k}^2 k!2^k(2n-2k)! $$

后面的式子相当于先选出 $k$ 个位置，$k$ 对情侣，对他们进行排列，情侣内部座位可以交换，剩下的人随意排。

二项式反演可得：

$$ f_k=\sum_{i=k}^n (-1)^{i-k}\binom{i}{k}g_i $$

暴力带入可得：

$$ f_k=\sum_{i=k}^n (-1)^{i-k}\binom{i}{k}\binom{n}{i}^2 i!2^i(2n-2i)! $$

$$ =\sum_{i=k}^n (-1)^{i-k} \dfrac{i!}{k!(i-k)!}\dfrac{(n!)^2}{(i!)^2((n-i)!)^2} i!2^i(2n-2i)! $$

$$ =\dfrac{(n!)^2}{k!}\sum_{i=k}^n (-1)^{i-k}\dfrac{2^i}{(i-k)!}\dfrac{(2n-2i)!}{((n-i)!)^2} $$

$$ =\dfrac{(n!)^2}{k!}\sum_{i=k}^n (-1)^{i-k}\dfrac{2^i}{(i-k)!}\binom{2n-2i}{n-i} $$

设 $m=n-k$，则原式

$$ =\dfrac{(n!)^22^k}{k!}\sum_{i=0}^m\dfrac{(-2)^i}{i!}\binom{2m-2i}{m-i} $$

设：

$$ A(x)=\sum_{i=0}^\infty \dfrac{(-2)^i}{i!} x^i,B(x)=\sum_{i=0}^\infty \binom{2i}{i} x^i $$

则答案是：

$$ \dfrac{(n!)^22^k}{k!}[x^{m}]A(x)\times B(x) $$

注意到 $A(x)=e^{-2x}$，但 $B(x)$ 好像不是那么显然。考虑到卡特兰数生成函数：

$$ C(x)=\dfrac{\sqrt{1-4x}}{2x}=\sum_{i=0}^{\infty} \dfrac{\binom{2i}{i}}{i+1}x^i $$

平移一下，再求导，即：

$$ (C(x)\times x)'= \sum_{i=0}^{\infty} \binom{2i}{i}x^i=\dfrac{1}{\sqrt{1-4x}}=B(x) $$

所以答案是：

$$ \dfrac{(n!)^22^k}{k!}[x^{m}]\dfrac{e^{-2x}}{\sqrt{1-4x}} $$

设 $F(x)=\dfrac{e^{-2x}}{\sqrt{1-4x}}$，考虑求他的系数。两边平方，将分母去掉可得：

$$ (1-4x)F^2=e^{-4x} $$

两边求导：

$$ (1-4x)\times 2F\times F'-4F^2=-4e^{-4x} $$

这时候左边仍然有卷积，还是不好做，所以考虑把右边的 $e^{-4x}$ 再带入原来的等式：

$$ (1-4x)\times 2F\times F'-4F^2=-4(1-4x)F^2 $$

消掉一个 $F$：

$$ (1-4x)\times 2F'-4F=-4(1-4x)F $$

移项之后对比系数可以得到：

$$ f_0=1,f_1=0,f_i\times i=4(i-1)\times f_{i-1}+8f_{i-2}(i\ge 2) $$

最后答案就是：

$$ \dfrac{(n!)^22^k}{k!}f_{n-k} $$

//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'

const int MAXN = 5e6 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int T, n, k, Ans;
int fac[MAXN], ifac[MAXN], Inv[MAXN], p2[MAXN], f[MAXN];

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
    return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

signed main () {
#ifdef FILE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    read(T);
    fac[0] = ifac[0] = Inv[1] = p2[0] = f[0] = 1, f[1] = 0;
    for(int i = 2; i < MAXN; ++i) {
        Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
        f[i] = (f[i - 1] * 4 * (i - 1) + f[i - 2] * 8) % mod * Inv[i] % mod;
    }
    for(int i = 1; i < MAXN; ++i) {
        fac[i] = fac[i - 1] * i % mod, ifac[i] = ifac[i - 1] * Inv[i] % mod;
        p2[i] = p2[i - 1] * 2 % mod;
    }
    while(T--) {
        read(n), read(k);
        Ans = fac[n] * fac[n] % mod * p2[k] % mod * ifac[k] % mod * f[n - k] % mod;
        printf("%lld\n", Ans);
    }
    return 0;
}

标签: 二项式反演

添加新评论