问题的两个版本是不同的。您可能想阅读这两个版本。只有两个版本都解决了,你才能进行黑客攻击。
给定一个长度为 $$$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$$$ 可能的方法。