← 返回题目列表

Codeforces · 1738/E

E. 平衡瘾君子

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

给定一个长度为 $$$n$$$ 的整数序列 $$$a_1, a_2, \dots, a_n$$$,你的任务是计算以 $$$998244353$$$ 为模的方法将其划分为几个非空连续子序列,以便子序列中的元素之和形成一个平衡序列。

如果对于每个 $$$1 \leq i \leq k$$$,$$$s_{i} = s_{k-i+1}$$$,则长度为 $$$k$$$ 的序列 $$$s_1, s_2, \dots, s_k$$$ 被认为是平衡的。例如,$$$[1, 2, 3, 2, 1]$$$ 和 $$$[1,3,3,1]$$$ 是平衡的,但 $$$[1,5,15]$$$ 不是平衡的。

形式上,每个分区都可以通过长度为 $$$k$$$ 的索引序列 $$$i_1, i_2, \dots, i_k$$$ 来描述,其中 $$$1 = i_1 < i_2 < \dots < i_k \leq n$$$ 使得

1、$$$k$$$是分区中非空连续子序列的数量;
2. 对于每个 $$$1 \leq j \leq k$$$,第 $$$j$$$ 个连续子序列以 $$$a_{i_j}$$$ 开始,并在 $$$a_{i_{j+1}}$$$ 之前结束,其中 $$$i_{k+1} = n + 1$$$。也就是说,第 $$$j$$$ 个子序列是 $$$a_{i_j}, a_{i_j+1}, \dots, a_{i_{j+1}-1}$$$。

令 $$$s_1, s_2, \dots, s_k$$$ 表示关于分区 $$$i_1, i_2, \dots, i_k$$$ 的子序列中的元素之和。形式上,对于每个$$$1 \leq j \leq k$$$,$$$$$$ s_j = \sum_{i=i_{j}}^{i_{j+1}-1} a_i = a_{i_j} + a_{i_j+1} + \dots + a_{i_{j+1}-1}。 $$$$$$ 例如,序列$$$[1,2,3,4,5,6]$$$的分区$$$[1\,|\,2,3\,|\,4,5,6]$$$由索引序列$$$[1,2,4]$$$描述,关于该分区的子序列中的元素之和为$$$[1,5,15]$$$。

如果以下至少一项成立,则两个分区 $$$i_1, i_2, \dots, i_k$$$ 和 $$$i'_1, i'_2, \dots, i'_{k'}$$$ (由索引序列描述)被认为是不同的。

- $$$k \neq k'$$$,
- $$$i_j \neq i'_j$$$ 对于某些 $$$1 \leq j \leq \min\left\{ k, k' \right\}$$$。

输入

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

每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \leq n \leq 10^5$$$),表示序列$$$a$$$的长度。

每个测试用例的第二行包含$$$n$$$整数$$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$),表示序列$$$a$$$的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出每个子序列中元素之和平衡的分区数,以 $$$998244353$$$ 为模。

示例

输入 #1

6
1
1000000000
2
1 1
4
0 0 1 0
5
1 2 3 2 1
5
1 3 5 7 9
32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出 #1

1
2
3
4
2
150994942

注意

对于第一个测试用例,只有一种方法可以对长度为 $$$1$$$ 的序列进行分区,它本身就是平衡的。

对于第二个测试用例,有 $$$2$$$ 对其进行分区的方法:

- 序列 $$$[1, 1]$$$ 本身,则 $$$s = [2]$$$ 是平衡的;
- 划分为两个子序列 $$$[1\,|\,1]$$$,则 $$$s = [1, 1]$$$ 是平衡的。

对于第三个测试用例,有 $$$3$$$ 对其进行分区的方法:

- 序列 $$$[0, 0, 1, 0]$$$ 本身,则 $$$s = [1]$$$ 是平衡的;
- $$$[0 \,|\, 0, 1 \,|\, 0]$$$,则 $$$s = [0, 1, 0]$$$ 平衡;
- $$$[0, 0 \,|\, 1 \,|\, 0]$$$,则 $$$s = [0, 1, 0]$$$ 是平衡的。

对于第四个测试用例,有 $$$4$$$ 对其进行分区的方法:

- 序列 $$$[1, 2, 3, 2, 1]$$$ 本身,则 $$$s = [9]$$$ 是平衡的;
- $$$[1, 2 \,|\, 3 \,|\, 2, 1]$$$,则 $$$s = [3, 3, 3]$$$ 平衡;
- $$$[1 \,|\, 2, 3, 2 \,|\, 1]$$$,则 $$$s = [1, 7, 1]$$$ 平衡;
- $$$[1 \,|\, 2 \,|\, 3 \,|\, 2 \,|\, 1]$$$,则 $$$s = [1, 2, 3, 2, 1]$$$ 是平衡的。

对于第五个测试用例,有 $$$2$$$ 对其进行分区的方法:

- 序列 $$$[1, 3, 5, 7, 9]$$$ 本身,则 $$$s = [25]$$$ 是平衡的;
- $$$[1, 3, 5 \,|\, 7 \,|\, 9]$$$,则 $$$s = [9, 7, 9]$$$ 是平衡的。

对于第六个测试用例,应计算每个可能的分区。所以答案是$$$2^{32-1} \equiv 150994942 \pmod {998244353}$$$。