← 返回题目列表

Codeforces · 2204/F

F. 分数和

中文机器翻译题面 查看原题

让我们调用 增加 分数的 $$$\frac{x}{y}$$$ 以下操作之一:

  • 要么将其分子$$$x$$$增加$$$1$$$;
  • 或者,如果分母 $$$y \gt 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)$$$ 表示为可以通过精确应用 $$$k$$$ 次增加运算从数组 $$$b$$$ 获得的最大分数和。

令 $$$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$$$,计算$$$\mathrm{MSF}$$$ 遍历数组 $$$a$$$ 的所有子数组并输出答案模数。

输入

第一行包含两个整数 $$$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}$$$ 的形式输出答案。

示例

输入
复制

5 4
2 3 5 2 3
0 1 2 10

输出
复制

232923695
332748137
931694761
133099397

注意

相应 $$$k$$$ 的答案为:$$$\frac{379}{30}$$$、$$$\frac{58}{3}$$$、$$$\frac{473}{15}$$$ 和 $$$\frac{2249}{15}$$$。