解题思路

我们记原序列为 $b_1, b_2, \dots, b_n$ ，问题需要回答 $m$ 个询问，每个询问给定一个区间 $[l, r]$ ，要求输出

\sum_{\substack{p\in [l, r] \\ p\ \text{是素数}}} W(p) \pmod{998244353},

其中

题目内容

小 L 获得了一个长度为 $n$ 的整数序列 $b_1, b_2, \dots, b_n$ ，他定义 $W(k)$ 为序列中所有长度为 $k$ 的连续子段之和的总和，即：

W(k) = \sum_{i=1}^{n-k+1} \sum_{j=i}^{i+k-1} b_j

现在他要进行 $m$ 次询问，每次询问给定一个区间 $[l, r]$ ，你需要回答该区间内所有为素数的长度 $p$ 对应的 $W(p)$ 的总和，结果对 $998244353$ 取模。

序列的长度 $n$ 不超过 $10^4$ ，询问次数 $m$ 不超过 $2 \times 10^5$ ，序列中的每个数均为正整数且不超过 $10^9$ 。

第一行包含两个正整数 $n$ 和 $m$ ，分别表示序列长度与询问次数。第二行包含 $n$ 个正整数 $b_1, b_2, \dots, b_n$ ，表示序列中的元素。