P4931 [MtOI2018] 情侣关系是否应该被打破？
摘要：P4931 [MtOI2018] 情侣？给我烧了！（加强版） 大意 (n) 对情侣，恰好 (k) 对在 (2 times n) 的电影院中坐一起的方案数。 思路 弱化版的可以去看 P4921 [MtOI2018] 情侣？给我烧
P4931 [MtOI2018] 情侣？给我烧了！（加强版）
大意
\(n\) 对情侣，恰好 \(k\) 对在 \(2 \times n\) 的电影院中坐一起的方案数。
思路
弱化版的可以去看 P4921 [MtOI2018] 情侣？给我烧了！
接下来进入正题，我们注意到刚刚的弱化版内的 $f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k D(n - k) $，且 \(D(n) = \sum_{i = 0} ^ {n} (-1) ^ i\binom{n}{i} ^ 2 i! 2 ^ i (2(n - i))!\)，我们考虑对于 \(g(n)\) 进行化简.
\[\sum_{i = 0} ^ {n}(-1) \binom{n}{i} ^ 2 i! 2 ^ i (2(n - i)) !
\\
= (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!}
\]
这里我们就可以直接做卷积了，但是问题在于这个题目要求的复杂度太过苛刻，卷积无法通过此题，我们考虑构造生成函数。
我们设：
\[F(x) = (n!) ^ 2 \sum_{i = 0} ^ n \frac{(2(n - i))!}{(n - i)! ^ 2} \frac{(-2) ^ i}{i!} x^i
\\
G[n] = \frac{(2n)!}{n!^2},P[n] = \frac{(-2) ^ i}{n !}
\]
那么，由离散卷积可知：
\[F(x) = G(x) * P(x)
\]
接下来，我们只需要分别对于 \(G(x)\) 和 \(P(x)\) 化简即可。
首先，对于 \(G(x)\) 来说，我们可以利用广义二项式定理，那么什么是广义二项式定理呢？对于任意实数 \(\alpha\)，都有 \((1 + z) ^ \alpha = \sum_{i = 0} ^ {\infty} \binom{\alpha}{i} z ^ i\)，那么说我们就可以化简 \(G(x)\) 了：
\[G(x) = \sum_{i = 0} \frac{(-2x) ^ i}{i!} x ^ i = \sum_{i = 0} \binom{2i}{i}x^i = \frac{1}{\sqrt{1 - 4x}}
\]
对于 \(P(x)\) 来说，直接化简：
\[P(x) = \sum_{i = 0} \frac{(-2x)!}{i!} = e ^ {-2x}
\]
经过化简，我们可以最终得到：
\[F(x) = \frac{e ^ {-2x}}{\sqrt{1 - 4x}}
\]
对于这个生成函数，为了得到与自身相关的式子进行递推，我们选择对其求导。
\[F'(x) = \frac{8x * e ^ {-2x}}{(1 - 4x) ^ \frac{3}{2}} = \frac{8x}{1 - 4x} F(x)
\]
整理一下：
\[F'(x) = 4xF'(x) + 8xF(x)
\]
提取 \([x ^ n]\) 的系数：
\[F'[n] = 4xF'[n - 1] + 8xF[n - 1]
\]
稍施小计，我们可以直接得到关于 \(F[n]\) 的递推式：
\[(n + 1)F[n + 1] = 4nF[n] + 8F[n - 1]
\]
你可能以为万事大吉了，但是问题是我们还有个 \((n!) ^ 2\) 的系数在最开始被我们提出去了，我们要把这玩意弄回来，带入 \(F[n] = \frac{D(n)}{n!} ^ 2\)：
\[(n + 1)\frac{D[n + 1]}{(n + 1)!} = 4n \frac{D[n]}{n!^2} + 8 \frac{D[n - 1]}{(n - 1)! ^ 2}
\]
我们就可以得到关于 \(D[n]\) 的递推式：
\[D[n + 1] = 4n(n + 1)D[n] + 8n ^ 2(n + 1)D[n - 1]
\]
直接 \(O(n)\) 递推即可。
代码
#include<iostream>
using namespace std;
#define int long long
const int MOD = 998244353;
const int MXN = 5000005;
int fac[MXN], inv[MXN], pow2[MXN], g[MXN];
int pw(int x, int y){
int res = 1;
x %= MOD;
while(y){
if(y & 1) res = (res * x) % MOD;
x = (x * x) % MOD;
y >>= 1;
}
return res;
}
void init(){
fac[0] = pow2[0] = 1;
for(int i = 1;i < MXN;i ++){
fac[i] = (fac[i - 1] * i) % MOD;
pow2[i] = (pow2[i - 1] * 2) % MOD;
}
inv[MXN - 1] = pw(fac[MXN - 1], MOD - 2);
for(int i = MXN - 2;i >= 0;i --) inv[i] = (inv[i + 1] * (i + 1)) % MOD;
g[0] = 1;
g[1] = 0;
for(int i = 2;i < MXN;i ++){
int A = (4 * i % MOD * (i - 1)) % MOD;
int B = (g[i - 1] + (2 * i - 2) * g[i - 2]) % MOD;
g[i] = (A * B) % MOD;
}
}
int C(int n, int k){
if(k < 0 || k > n) return 0;
return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int f(int n, int k){
int res = (C(n, k) * C(n, k)) % MOD;
res = (res * fac[k]) % MOD;
res = (res * pow2[k]) % MOD;
res = (res * g[n - k]) % MOD;
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
init();
int T, n, k;
cin >> T;
while(T --){
cin >> n >> k;
cout << f(n, k) << '\n';
}
return 0;
}