CF2228E1.Amanojaku and Sequence (Easy Version)

Tinkerbell of Inequality

— Taboo Japan Disentanglement

This is the easy version of the problem. The difference between the versions is that in this version, $q=1$ and $\mathrm{op}=2$. You can hack only if you solved all versions of this problem.

For a sequence $s$, let $|s|$ denote its length.

For a non-negative integer sequence $c$, define $f(c)$ as the sum of the squares of its prefix sums: $$ f(c)=\sum_{i=1}^{{|c|}\left(\sum_{j=1}}{i} c_j\right)^2. $$

Now define $g(b,m)$ as follows.

Let $b$ be an integer sequence such that $b_i\ge -1$ for every $i$, and let $m$ be a non-negative integer. A non-negative integer sequence $c$ is called valid for $(b,m)$ if all of the following conditions hold:

• $|c|=|b|$;
• $\sum_{i=1}^{|c|} c_i=m$;
• for every $1\le i\le |b|$, if $b_i\ge 0$, then $c_i=b_i$; otherwise, if $b_i=-1$, then $c_i$ may be any non-negative integer.

The value $g(b,m)$ is defined as the sum of $f(c)$ over all valid sequences $c$ for $(b,m)$. If there is no such sequence, then $g(b,m)=0$.

You are given an array $a$ of length $n$, where $a_i\ge -1$, and $q$ queries of the following one type:

• Given three integers $l$, $r$, and $m$, compute $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$, where $[a_l,a_{l+1},\ldots,a_r]$ denotes the subarray$^{\text{∗}}$ of $a$ from position $l$ to position $r$.

$^{\text{∗}}$An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

不等式的 tinkerbelle

——禁忌日本解缠问题

本题为简单版本。两个版本的区别在于：在本版本中，$q=1$ 且 $\mathrm{op}=2$。仅当您已解决本题所有版本后，才可进行 hack。

对于一个序列 $s$，记 $|s|$ 表示其长度。

对于一个非负整数序列 $c$，定义 $f(c)$ 为其前缀和的平方之和：

$$f(c)=\sum_{i=1}^{|c|}\left(\sum_{j=1}^{i} c_j\right)^2.$$

现定义 $g(b,m)$ 如下：

设 $b$ 是一个整数序列，满足对每个 $i$ 都有 $b_i \ge -1$；设 $m$ 是一个非负整数。若一个非负整数序列 $c$ 满足以下全部条件，则称其对 $(b,m)$ 有效：

• $|c|=|b|$；
• $\sum_{i=1}^{|c|} c_i=m$；
• 对每个 $1\le i\le |b|$，若 $b_i\ge 0$，则 $c_i=b_i$；否则（即 $b_i=-1$），$c_i$ 可取任意非负整数。

定义 $g(b,m)$ 为所有对 $(b,m)$ 有效的序列 $c$ 对应的 $f(c)$ 值之和。若不存在这样的序列，则 $g(b,m)=0$。

给定一个长度为 $n$ 的数组 $a$，其中每个 $a_i \ge -1$，以及 $q$ 个如下类型的查询：

• 给定三个整数 $l$、$r$ 和 $m$，计算 $g([a_l,a_{l+1},\ldots,a_r],m)$ 对 $998\,244\,353$ 取模的结果，其中 $[a_l,a_{l+1},\ldots,a_r]$ 表示数组 $a$ 从位置 $l$ 到位置 $r$ 的子数组$^{\text{∗}}$。

$^{\text{∗}}$ 若数组 $a$ 可通过从数组 $b$ 的开头删除若干（可能为零或全部）元素、再从结尾删除若干（可能为零或全部）元素而得到，则称 $a$ 是 $b$ 的一个子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

For each test case, the first line contains two integers $n$ and $q$ ($1\leq n\leq 3\cdot 10^5$, $q=1$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-1\leq a_i\leq 10^6$).

Then $q$ lines follow. Each line describes a query in the following format. The first integer $\textrm{op}$ is $2$.

• $2\,l\,r\,m$: compute $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$ ($1\leq l\leq r\leq n$, $0\leq m\leq 10^6$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

对于每个测试用例，第一行包含两个整数 $n$ 和 $q$（$1\leq n\leq 3\cdot 10^5$，$q=1$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-1\leq a_i\leq 10^6$）。

接下来是 $q$ 行，每行描述一个查询，格式如下。第一个整数 $\textrm{op}$ 恒为 $2$。

• $2\,l\,r\,m$：计算 $g([a_l,a_{l+1},\ldots,a_r],m)$ 对 $998\,244\,353$ 取模的结果（其中 $1\leq l\leq r\leq n$，$0\leq m\leq 10^6$）。

保证所有测试用例的 $n$ 之和不超过 $3\cdot 10^5$。

For each test case, for every query of the second type, output the value of $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$ on a line.

对于每个测试用例，对每一个第二类查询，在一行中输出 $g([a_l,a_{l+1},\ldots,a_r],m)$ 对 $998\,244\,353$ 取模的值。

In the first test case:

$l=r=2$ and $m=2$. The subarray is $[a_2]=[-1]$, so the only valid sequence is $c=[2]$. Thus, the answer is $2^2=4$.

In the third test case:

$l=4$, $r=5$, and $m=8$. The subarray is $[a_4,a_5]=[6,-1]$. Since $c_1$ is fixed at $6$ and $c_1+c_2=m$, we obtain $c=[6,2]$. The prefix sums are $6$ and $8$, giving $$ f(c)=6^2+(6+2)2=36+64=100. $$

In the seventh test case:

The subarray is $[a_1,a_2]=[-1,-1]$. All valid sequences satisfy $c_1+c_2=5$ with $c_1,c_2\ge 0$, namely $[0,5],[1,4],\ldots,[5,0]$. Summing $f(c)$ over all such sequences yields $205$.

在第一个测试用例中：

$l=r=2$ 且 $m=2$。子数组为 $[a_2]=[-1]$，因此唯一合法的序列是 $c=[2]$。故答案为 $2^2=4$。

在第三个测试用例中：

$l=4$，$r=5$，且 $m=8$。子数组为 $[a_4,a_5]=[6,-1]$。由于 $c_1$ 固定为 $6$，且 $c_1+c_2=m$，可得 $c=[6,2]$。其前缀和依次为 $6$ 和 $8$，因此

$$f(c)=6^2+(6+2)^2=36+64=100.$$

在第七个测试用例中：

子数组为 $[a_1,a_2]=[-1,-1]$。所有合法序列满足 $c_1+c_2=5$ 且 $c_1,c_2\ge 0$，即 $[0,5],[1,4],\ldots,[5,0]$。对所有此类序列求 $f(c)$ 的和，结果为 $205$。