配点 : 100 点
問題文
P 是质数 除以 998244353 。 对多项式 f(x) 定义以下一系列操作。 多项式
- f(x) 和 按字典顺序比较 (1 + x^k)g(x) 各项系数对 P 的余数相等的正整数 k 和有限次数的多项式 g(x)\neq 0 。
- 然后,f(x) 在上述 g(x) 替换为 2^k 的分数。
某个多项式上,这个操作可以进行任意次数,以获得的分数总和的最大值是多项式的 美容 。
数列 A=(A_0,\ldots,A_{N - 1}) 和 按字典顺序比较 Q 查询。 在查询
i 个查询是一个整数 查找 l_i,r_i 已知,因此多项式 \displaystyle f(x) = \sum_{j=0}^{r_i - l_i}A_{j + l_i}x^{j} 可以得到第 美容 该值应乘以 P 求除以后的余数。
但是,操作中 g(x) 的系数仅限于低于 998244353 的非负整数。(13:10 更新)
制約
- 所有输入均为整数
- 2\leq N \leq 2000
- 1\leq Q \leq 2000
- 0\leq A_i < P
- 0\leq l_i < r_i \leq N - 1
入力
输入是按以下格式从标准输入给出的。
N Q
A_{0} \ldots A_{N - 1}
l_1 r_1
\vdots
l_{Q} r_{Q}
出力
Q 行。
各 i (1\leq i \leq Q) , 当我输入 i 在线 i 个查询的答案。
入力例 1
6 3 1 2 1 1 1 1 0 2 2 5 2 4
出力例 1
4 6 0
关于第一个查询,f(x) = (1 + 2x + x^2) 是这样, k = 1 最好选择两次。
关于第二个查询,f(x) = (1 + x + x^2 + x^3)是这样,但在第一次操作中k = 1,在第二次操作中k = 2 最好选择。
关于第三个查询,f(x) = (1 + x + x^2)是这样,但一次操作也无法进行。
入力例 2
11 2 1 1 0 0 0 0 0 0 0 1 1 0 10 4 5
出力例 2
514 0
在第一个查询中,f(x) = (1 + x + x^9 + x^{10}) 的美丽度会被计算,在第二个查询中,f(x) = 0 的美丽度会被计算。