AT_utpc2021_k.Divide Polynomials by #Subset Sums

设定素数 $P = 998244353$。对于一个多项式 $f(x)$，我们定义以下操作：

1. 选择一个正整数 $k$ 和一个有限次非零多项式 $g(x)$，使得 $f(x)$ 和 $(1 + x^k)g(x)$ 在每个次数上的系数对 $P$ 取模后相等。
2. 将 $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$ 的非负整数。

标准输入按以下格式给出：

$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$ 行输出查询的答案。

• 所有输入都为整数。
• $2 \leq N \leq 2000$
• $1 \leq Q \leq 2000$
• $0 \leq A_i < 998244353$
• $0 \leq l_i < r_i \leq N$

样例解释 1

针对第一个查询，$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

在第一个查询中，处理 $f(x) = 1 + x + x^9 + x^{10}$ 的 美；在第二个查询中，计算 $f(x) = 0$ 的 美。

本翻译由 AI 自动生成