CF2204F Sum of Fractions

我们称对分数 $\frac{x}{y}$ 的一次增加操作为以下两种操作之一： - 将分子的 $x$ 增加 $1$； - 或者，如果分母 $y > 1$，将分母 $y$ 减少 $1$。 注意，进行增加操作后，分数不需要约分。例如，如果你有分数 $\frac{3}{7}$ 并将分母减少 $1$，结果应为 $\frac{3}{6}$，而不是 $\frac{1}{2}$。 现在，给定一个整数数组 $b_1, b_2, \dots, b_m$ 和一个整数 $k$。我们执行如下算法： 1. 构造数组 $\frac{1}{b_1}, \frac{1}{b_2}, \dots, \frac{1}{b_m}$。 2. 任意选择一个分数并对其执行一次“增加”操作。 3. 重复上一步，重复 $k$ 次（同一个分数允许被多次选择）。 4. 计算最终所有分数的和。 我们定义 $\mathrm{MSF}(b, k)$ 为：对数组 $b$ 执行恰好 $k$ 次“增加”操作后，所有分数和的最大值。 记 $a[l\dots r]$ 表示数组 $a$ 的子区间 $a_l, a_{l+1}, \dots, a_r$。 现给定两个整数数组 $a_1,a_2,\dots, a_n$ 和 $k_1, k_2, \dots, k_m$。对于每个 $k_i$，计算 $$ \left( \sum\limits_{l = 1}^{n}{\sum\limits_{r = l}^{n}\mathrm{MSF}(a[l \dots r], k_i)} \right) \bmod 998\,244\,353. $$ 换句话说，对于每个 $k_i$，计算数组 $a$ 的所有子区间的 $\mathrm{MSF}$ 的和，并输出结果模 $998\,244\,353$。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 5 \cdot 10^5$），分别表示数组 $a$ 和 $k$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^8$），表示数组 $a$。 第三行包含 $m$ 个整数 $k_1, k_2, \dots, k_m$（$0 \le k_1 \le k_2 \le \dots \le k_m \le 10^8$），表示按非递减顺序排列的数组 $k$。

对于每个 $k_i$，输出一个整数，表示所有子区间的 $\mathrm{MSF}$ 之和模 $998\,244\,353$ 的结果。 可以证明，每个答案都可表示为既约分数 $\frac{P}{Q}$，其中 $Q \not\equiv 0 \pmod{998\,244\,353}$。因此，输出形式为 $P \cdot Q^{-1} \pmod{998\,244\,353}$。

对于给定的 $k$，对应答案依次为：$\frac{379}{30}$、$\frac{58}{3}$、$\frac{473}{15}$ 和 $\frac{2249}{15}$。 由 ChatGPT 5 翻译