← 返回题目列表

Codeforces · 2053/I2

I2. 深情阵(硬版)

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

请注意,此声明与官方回合中使用的版本不同。该语句已更正为可解决的版本。在正式回合中,所有针对此问题的提交都已被删除。

这是问题的困难版本。版本之间的区别在于,在这个版本中,您需要计算不同数组的值的总和。只有解决了该问题的所有版本,您才能破解。

Iris 珍藏着一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。她知道这个数组有一个有趣的属性:所有元素的最大绝对值小于或等于所有元素的总和,即$$$\max(\lvert a_i\rvert) \leq \sum a_i$$$。

Iris 将数组的无聊度定义为其最大子数组$$$^{\text{*}}$$$ 之和。

Iris 的生日快到了,Victor 准备送她另一个数组 $$$b_1, b_2, \ldots, b_m$$$ 作为礼物。由于一些看似显而易见的原因,他决定数组 $$$b_1, b_2, \ldots, b_m$$$ 应该具有以下属性。

- $$$a_1, a_2, \ldots, a_n$$$ 应该是 $$$b_1, b_2, \ldots, b_m$$$ 的子序列$$$^{\text{†}}$$$。
- 两个数组的总和相同。即 $$$\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$$$。
- $$$b_1, b_2, \ldots, b_m$$$ 的无聊度是最小的。
- 在无聊度最小的数组中,数组 $$$b$$$ 的长度(即 $$$m$$$)是最小的。而这样的话,艾丽丝就会第一时间明白他的心思!

对于满足上述所有条件的可能数组 $$$b_1, b_2, \ldots, b_m$$$,Victor 将数组的值定义为数组 $$$a$$$ 作为数组 $$$b$$$ 中的子序列出现的次数。也就是说,他计算了 $$$1\le c_1< c_2< \ldots< c_n\le m$$$ 的数组 $$$c_1, c_2, \ldots, c_{n}$$$ 的数量,并且对于所有整数 $$$i$$$ 满足 $$$1\le i\le n$$$ 的情况,$$$b_{c_{i}}=a_i$$$ 被满足,并将其设为值数组$$$b$$$。

即使有上述限制,可能的礼物仍然太多。所以 Victor 要求你计算所有可能的数组 $$$b_1, b_2, \ldots, b_m$$$ 的值的总和。由于答案可能很大,Victor 只需要模 $$$998\,244\,353$$$ 即可。他向你承诺:如果你成功帮助他,他将与你分享艾丽丝的生日蛋糕。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^6$$$) — 数组 $$$a_1, a_2, \ldots, a_n$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - 初始数组。保证 $$$\max(\lvert a_i\rvert) \leq \sum a_i$$$。

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

输出

对于每个测试用例,输出一行包含一个整数:有效数组 $$$b_1, b_2, \ldots, b_m$$$ 的值之和,模 $$$998\,244\,353$$$。

示例

输入 #1

5
4
1 2 3 4
4
2 -3 2 2
4
1 -2 2 1
10
2 -7 6 3 -1 4 2 -5 8 -4
20
4 -2 4 3 -2 1 5 2 3 6 -5 -1 -4 -2 -3 5 -3 1 -4 1

输出 #1

1
2
2
20
1472

注意

在第一个测试用例中,$$$a=[1, 2, 3, 4]$$$。唯一可能的数组 $$$b$$$ 是 $$$[1, 2, 3, 4]$$$,其值为 $$$1$$$。

在第二个测试用例中,$$$a=[2, -3, 2, 2]$$$。可能的数组 $$$b$$$ 为 $$$[1, 2, -3, 2, -1, 2]$$$ 和 $$$[2, 1, -3, 2, -1, 2]$$$。两个数组的值都是 $$$1$$$。

在第三个测试用例中,$$$a=[1, -2, 2, 1]$$$。唯一可能的数组 $$$b$$$ 是 $$$[1, 1, -2, 2, -1, 1]$$$。它的值为 $$$2$$$,因为我们可以找到数组 $$$c=[1,3,4,6]$$$ 或 $$$[2,3,4,6]$$$。也就是说,数组$$$a$$$在$$$b$$$中出现了两次,所以答案是$$$2$$$。