← 返回题目列表

Codeforces · 1984/C2

C2. 幅度(硬版)

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

问题的两个版本是不同的。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$。从 $$$c = 0$$$ 开始。然后,对于从 $$$1$$$ 到 $$$n$$$ (按递增顺序)的每个 $$$i$$$ 执行以下操作之一:

- 选项 $$$1$$$:将 $$$c$$$ 设置为 $$$c + a_i$$$。
- 选项 $$$2$$$:将 $$$c$$$ 设置为 $$$|c + a_i|$$$,其中 $$$|x|$$$ 是 $$$x$$$ 的绝对值。

令$$$c$$$ 经过上述过程后的最大最终值等于$$$k$$$。找出导致 $$$c = k$$$ 的唯一过程的数量。如果在任何索引 $$$i$$$ 处,一个过程选择了选项 $$$1$$$,另一个过程选择了选项 $$$2$$$,则两个过程是不同的,即使在该回合之后两个过程的 $$$c$$$ 值相等。

由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$)。

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

输出

对于每个测试用例,输出一个整数 - 导致 $$$c = k$$$ 的唯一过程的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5
4
2 -5 3 -3
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4

输出 #1

12
256
1
8
16

注意

在第一个测试用例中,可以证明 $$$c$$$ 的最大最终值为 $$$3$$$。有 $$$12$$$ 方法可以实现此目的,因为为了获得 $$$3$$$,我们必须在索引 $$$2$$$ 或 $$$4$$$ 或两者上取绝对值,从而产生 $$$3$$$ 方法。对于其他两个索引,无论我们是否取绝对值,它都不会改变值,因此我们有 $$$2 \cdot 2 = 4$$$ 方法。总共,我们有 $$$3 \cdot 4 = 12$$$ 种方式。

在第二个测试用例中,取绝对值永远不会改变任何东西,因此对于每个索引,我们可以取绝对值,也可以不取绝对值。这给了我们 $$$2^8 = 256$$$ 可能的方法。