← 返回题目列表

Codeforces · 2228/E1

E1. 天野雀和序列(简易版)

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

不平等的小叮当
— 禁忌日本解脱

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$q=1$$$ 和$$$\mathrm{op}=2$$$。只有解决了该问题的所有版本,您才能破解。

对于序列 $$$s$$$,令 $$$|s|$$$ 表示其长度。

对于非负整数序列 $$$c$$$,将 $$$f(c)$$$ 定义为其前缀和的平方和: $$f(c)=\sum_{i=1}^{|c|}\left(\sum_{j=1}^{i} c_j\right)^2.$$

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

令 $$$b$$$ 为整数序列,使得 $$$b_i\ge -1$$$ 对于每个 $$$i$$$,并令 $$$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$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

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

示例

输入
复制

10
5 1
4 -1 7 6 -1
2 2 2 2
5 1
4 -1 8 6 -1
2 3 3 0
5 1
4 -1 8 6 -1
2 4 5 8
5 1
4 -1 8 6 7
2 3 5 21
5 1
4 -1 8 6 7
2 3 5 22
4 1
-1 -1 -1 -1
2 1 1 4
4 1
-1 -1 -1 -1
2 1 2 5
4 1
-1 -1 -1 -1
2 1 3 6
4 1
-1 -1 -1 -1
2 1 4 7
4 1
-1 -1 3 -1
2 1 4 5

输出
复制

4
0
100
701
0
16
205
1736
12180
286

注意

在第一个测试用例中:

$$$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$$$。