P4931 [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;
}