题意理解

有 $n$ 个随机变量，每个变量在 $[1,D]$ 中均匀随机取值。

我们要把值相同的两个变量放进一个瓶子，每个瓶子恰好装两个相同值的变量。

问：能装出至少 $m$ 个瓶子的概率是多少？输出概率乘 $D^n$ 后对 $998244353$ 取模。

---

核心难点

1. $n$ 和 $m$ 极大：$n, m \le 10^9$，需要生成函数或组合公式
2. 配对约束：每个颜色出现的次数必须是偶数才能完全配对
3. 至少 $m$ 个瓶子：需要容斥或生成函数

---

关键思路：生成函数与组合计数

第一步：重新表述问题

设颜色 $i$ 出现的次数为 $c_i$，那么用颜色 $i$ 能装出的瓶子数为 $\lfloor c_i/2 \rfloor$。

总瓶子数 = $\sum_{i=1}^D \lfloor c_i/2 \rfloor$

我们需要总瓶子数 $\ge m$ 的方案数。

---

第二步：生成函数方法

考虑每个颜色的生成函数。对于一种颜色，出现次数为 $c$ 的方案数为 $\frac{1}{c!}$（在 EGF 中），且能贡献 $\lfloor c/2 \rfloor$ 个瓶子。

但 $\lfloor c/2 \rfloor$ 不好直接处理。我们换一种角度：

---

第三步：关键转化

设 $a_i$ = 颜色 $i$ 出现的次数模 $2$ 的余数（即 $0$ 或 $1$）。

• 如果 $a_i = 0$，那么颜色 $i$ 的所有珍珠都能配对
• 如果 $a_i = 1$，那么颜色 $i$ 会剩下一颗珍珠无法配对

设 $t$ = 满足 $a_i = 1$ 的颜色数（即剩余单颗珍珠的颜色数）。

那么总瓶子数 = $\frac{n - t}{2}$

所以条件 $\frac{n - t}{2} \ge m$ 等价于 $t \le n - 2m$

---

第四步：问题转化

现在问题变成：求有多少种颜色出现情况，使得剩余单颗珍珠的颜色数 $t \le n - 2m$。

---

第五步：计数方法

我们使用指数生成函数（EGF）：

• 对于每个颜色，如果它最后剩余 $0$ 颗单珠（即出现偶数次），其 EGF 为 $\cosh(x) = \frac{e^x + e^{-x}}{2}$
• 如果最后剩余 $1$ 颗单珠（即出现奇数次），其 EGF 为 $\sinh(x) = \frac{e^x - e^{-x}}{2}$

设我们钦定有 $t$ 种颜色剩余 $1$ 颗单珠，其余 $D-t$ 种颜色剩余 $0$ 颗单珠。

那么方案数的 EGF 为：

$$\binom{D}{t} (\sinh(x))^t (\cosh(x))^{D-t}$$

---

第六步：提取系数

我们需要 $x^n$ 的系数乘 $n!$（因为这是 EGF）。

利用二项式展开：

$$(\sinh(x))^t (\cosh(x))^{D-t} = \frac{(e^x - e^{-x})^t (e^x + e^{-x})^{D-t}}{2^D} $$

展开后，每一项形如 $e^{kx}$，其中 $k$ 的取值为：

$$k = (t - 2i) + (D - t - 2j) = D - 2(i+j)$$

其中 $i = 0..t$, $j = 0..D-t$

实际上可以化简为：

$$= \frac{1}{2^D} \sum_{i=0}^D \sum_{j=0}^t (-1)^j \binom{t}{j} \binom{D-t}{i} e^{(D-2i-2j)x} $$

$x^n$ 的系数为 $\frac{1}{2^D} \sum_{i=0}^D \sum_{j=0}^t (-1)^j \binom{t}{j} \binom{D-t}{i} \frac{(D-2i-2j)^n}{n!}$

乘 $n!$ 后得到方案数。

---

第七步：最终公式

令 $k = i+j$，经过组合化简，最终得到：

设 $f(t)$ = 恰有 $t$ 种颜色剩余单珠的方案数，则：

$$f(t) = \binom{D}{t} \frac{1}{2^D} \sum_{i=0}^D (D-2i)^n \sum_{j=0}^t (-1)^j \binom{t}{j} \binom{D-t}{i-j} $$

内层求和可以化简，最终：

$$f(t) = \binom{D}{t} \frac{1}{2^D} \sum_{i=0}^D (D-2i)^n \binom{D-2t}{i-t} (-1)^{i-t} $$

答案 = $\sum_{t=0}^{\min(D, n-2m)} f(t)$

---

第八步：算法实现

1. 预处理组合数
2. 枚举 $t$ 从 $0$ 到 $\min(D, n-2m)$
3. 对于每个 $t$，枚举 $i$ 计算内层和
4. 累加得到答案

复杂度 $O(D^2)$，但 $D \le 10^5$ 时需要用 NTT 优化内层求和。

---

关键代码框架

// 预处理阶乘和逆元
init_comb(D);

ll ans = 0;
for (int t = 0; t <= min(D, n - 2*m); t++) {
    ll sum = 0;
    for (int i = t; i <= D - t; i++) {
        ll term = C(D - 2*t, i - t) * qpow(D - 2*i, n) % MOD;
        if ((i - t) % 2) term = MOD - term;
        sum = (sum + term) % MOD;
    }
    sum = sum * C(D, t) % MOD * qpow(qpow(2, D), MOD-2) % MOD;
    ans = (ans + sum) % MOD;
}

---

总结

这道题的核心在于：

1. 将瓶子数转化为单珠颜色数
2. 使用生成函数计数
3. 利用双曲函数的组合意义
4. 通过二项式展开化简求和

最终得到一个可以计算的组合公式，通过枚举和预处理能够在合理时间内求解。