题解

问题分析

题目要求计算经过 $d$ 个夜晚后，宝石岛上 $n$ 个居民中宝石数前 $r$ 名的总和的期望（对 $998244353$ 取模）。初始时每个居民有 $1$ 颗宝石，每晚恰好有 $1$ 颗宝石分裂为 $2$ 颗（即总宝石数每天增加 $1$），$d$ 天后总宝石数为 $n + d$。

核心洞察

1. 总宝石数的确定性：$d$ 天后总宝石数固定为 $S = n + d$，这是后续推导的基础。
2. 对称性与期望线性性：居民初始状态对称，可通过组合数学刻画分裂过程的概率分布。前 $r$ 名总和的期望可转化为对“单个居民进入前 $r$ 名的概率”与“其宝石数期望”的加权求和。
3. 组合数的意义：分裂过程的路径数与组合数 $C(d + n - 1, n - 1)$ 相关，这是概率计算的归一化因子。

算法步骤

1. 预处理阶乘与逆阶乘：为快速计算组合数 $C(n, k)$，预先计算阶乘 $jc$ 及逆阶乘 $inv\_jc$（模 $998244353$），支持 $O(1)$ 组合数查询。

2. 计算辅助数组 $f$：通过类似埃氏筛的方法计算 $f$ 数组，其本质是利用数论变换（如莫比乌斯反演）处理累加项，用于刻画分裂次数的分布特征。具体来说，对每个 $i$，通过遍历其倍数 $j$ 累加 $f[i \cdot j]$ 到 $f[j]$，实现高效的数论函数求和。

3. 期望公式的计算：利用包含-排斥原理，通过组合数 $C(n, k)$、符号项 $(-1)^{k-r}$ 及辅助数组 $f$，构造前 $r$ 名总和的期望表达式。最终结果为该表达式除以归一化因子 $C(d + n - 1, n - 1)$（模意义下的除法）。

代码解析

• 预处理模块：init 函数计算阶乘 $jc$ 和逆阶乘 $inv\_jc$，为组合数计算提供支持。
• 辅助数组 $f$ 的计算：通过筛法遍历 $1$ 到 $d$，对每个 $i$ 及其倍数 $j$ 累加 $f[i \cdot j]$ 到 $f[j]$，这一步利用了数论函数的 multiplicative 性质，高效处理累加项。
• 期望计算：res 的求和式结合了组合数、符号项和 $f$ 数组，刻画了前 $r$ 名总和的期望。最终除以 $C(d + n - 1, n - 1)$ 得到归一化后的期望，输出模 $998244353$ 的结果。

复杂度分析

• 时间复杂度：$O(n + d \log d)$。预处理阶乘为 $O(N)$（$N$ 为 $3 \times 10^7$），筛法计算 $f$ 数组为 $O(d \log d)$（类似埃氏筛的时间复杂度），最终求和为 $O(n)$。
• 空间复杂度：$O(N)$，用于存储阶乘、逆阶乘和辅助数组 $f$。

综上，该算法通过组合数学与数论工具，结合概率期望的性质，高效求解了前 $r$ 名宝石数总和的期望，适用于大规模输入数据。