Balance Addicts

题意翻译

给定一个长度为 $n$ 的序列 $a$，对于每一种将 $a$ 划分成若干个子串的方式，我们设有当前划分有 $k$ 个子串，分别描述为 $(l_1,r_1),(l_2,r_2)\dots(l_k,r_k)$，定义长度为 $k$ 的数组 $s$ 满足 $s_i=\sum\limits^{r_i}_{j=l_j}a_j$。如果 $s$ 是一个回文数组，那么我们称这一种划分方式是好的。 求 $a$ 有多少好的划分。

题目描述

Given an integer sequence $ a_1, a_2, \dots, a_n $ of length $ n $ , your task is to compute the number, modulo $ 998244353 $ , of ways to partition it into several non-empty continuous subsequences such that the sums of elements in the subsequences form a balanced sequence. A sequence $ s_1, s_2, \dots, s_k $ of length $ k $ is said to be balanced, if $ s_{i} = s_{k-i+1} $ for every $ 1 \leq i \leq k $ . For example, $ [1, 2, 3, 2, 1] $ and $ [1,3,3,1] $ are balanced, but $ [1,5,15] $ is not. Formally, every partition can be described by a sequence of indexes $ i_1, i_2, \dots, i_k $ of length $ k $ with $ 1 = i_1 < i_2 < \dots < i_k \leq n $ such that 1. $ k $ is the number of non-empty continuous subsequences in the partition; 2. For every $ 1 \leq j \leq k $ , the $ j $ -th continuous subsequence starts with $ a_{i_j} $ , and ends exactly before $ a_{i_{j+1}} $ , where $ i_{k+1} = n + 1 $ . That is, the $ j $ -th subsequence is $ a_{i_j}, a_{i_j+1}, \dots, a_{i_{j+1}-1} $ . There are $ 2^{n-1} $ different partitions in total. Let $ s_1, s_2, \dots, s_k $ denote the sums of elements in the subsequences with respect to the partition $ i_1, i_2, \dots, i_k $ . Formally, for every $ 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}. $ $ For example, the partition $ \[1\\,|\\,2,3\\,|\\,4,5,6\] $ of sequence $ \[1,2,3,4,5,6\] $ is described by the sequence $ \[1,2,4\] $ of indexes, and the sums of elements in the subsequences with respect to the partition is $ \[1,5,15\] $ .</p><p>Two partitions $ i\_1, i\_2, \\dots, i\_k $ and $ i'\_1, i'\_2, \\dots, i'\_{k'} $ (described by sequences of indexes) are considered to be different, if at least one of the following holds. </p><ul> <li> $ k \\neq k' $ , </li><li> $ i\_j \\neq i'\_j $ for some $ 1 \\leq j \\leq \\min\\left\\{ k, k' \\right\\}$.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^5 $ ), indicating the length of the sequence $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ), indicating the elements of the sequence $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output the number of partitions with respect to which the sum of elements in each subsequence is balanced, modulo $ 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

说明

For the first test case, there is only one way to partition a sequence of length $ 1 $ , which is itself and is, of course, balanced. For the second test case, there are $ 2 $ ways to partition it: - The sequence $ [1, 1] $ itself, then $ s = [2] $ is balanced; - Partition into two subsequences $ [1\,|\,1] $ , then $ s = [1, 1] $ is balanced. For the third test case, there are $ 3 $ ways to partition it: - The sequence $ [0, 0, 1, 0] $ itself, then $ s = [1] $ is balanced; - $ [0 \,|\, 0, 1 \,|\, 0] $ , then $ s = [0, 1, 0] $ is balanced; - $ [0, 0 \,|\, 1 \,|\, 0] $ , then $ s = [0, 1, 0] $ is balanced. For the fourth test case, there are $ 4 $ ways to partition it: - The sequence $ [1, 2, 3, 2, 1] $ itself, then $ s = [9] $ is balanced; - $ [1, 2 \,|\, 3 \,|\, 2, 1] $ , then $ s = [3, 3, 3] $ is balanced; - $ [1 \,|\, 2, 3, 2 \,|\, 1] $ , then $ s = [1, 7, 1] $ is balanced; - $ [1 \,|\, 2 \,|\, 3 \,|\, 2 \,|\, 1] $ , then $ s = [1, 2, 3, 2, 1] $ is balanced. For the fifth test case, there are $ 2 $ ways to partition it: - The sequence $ [1, 3, 5, 7, 9] $ itself, then $ s = [25] $ is balanced; - $ [1, 3, 5 \,|\, 7 \,|\, 9] $ , then $ s = [9, 7, 9] $ is balanced. For the sixth test case, every possible partition should be counted. So the answer is $ 2^{32-1} \equiv 150994942 \pmod {998244353} $ .

**平衡上瘾**

**题意翻译**：
给定一个长度为 $ n $ 的序列 $ a $，对于每一种将 $ a $ 划分成若干个子串的方式，我们设有当前划分有 $ k $ 个子串，分别描述为 $ (l_1,r_1),(l_2,r_2)\dots(l_k,r_k) $，定义长度为 $ k $ 的数组 $ s $ 满足 $ s_i=\sum\limits^{r_i}_{j=l_j}a_j $。如果 $ s $ 是一个回文数组，那么我们称这一种划分方式是好的。

求 $ a $ 有多少好的划分。

**题目描述**：
给定一个整数序列 $ a_1, a_2, \dots, a_n $ 的长度 $ n $，你的任务是计算将序列划分为几个非空连续子序列的方式的数量，使得子序列中元素的和对998244353取模后形成一个平衡序列。

一个长度为 $ k $ 的序列 $ s_1, s_2, \dots, s_k $ 被认为是平衡的，如果对于每一个 $ 1 \leq i \leq k $，都有 $ s_i = s_{k-i+1} $。例如，$ [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} $。

总共有 $ 2^{n-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} $。

**输入输出格式**：

**输入格式**：
每个测试包含多个测试用例。第一行包含一个整数 $ 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的序列只有一种划分方式，即它本身，显然是平衡的。

对于第二个测试用例，有两种划分方式：

- 序列**平衡上瘾** **题意翻译**： 给定一个长度为 $ n $ 的序列 $ a $，对于每一种将 $ a $ 划分成若干个子串的方式，我们设有当前划分有 $ k $ 个子串，分别描述为 $ (l_1,r_1),(l_2,r_2)\dots(l_k,r_k) $，定义长度为 $ k $ 的数组 $ s $ 满足 $ s_i=\sum\limits^{r_i}_{j=l_j}a_j $。如果 $ s $ 是一个回文数组，那么我们称这一种划分方式是好的。 求 $ a $ 有多少好的划分。 **题目描述**： 给定一个整数序列 $ a_1, a_2, \dots, a_n $ 的长度 $ n $，你的任务是计算将序列划分为几个非空连续子序列的方式的数量，使得子序列中元素的和对998244353取模后形成一个平衡序列。 一个长度为 $ k $ 的序列 $ s_1, s_2, \dots, s_k $ 被认为是平衡的，如果对于每一个 $ 1 \leq i \leq k $，都有 $ s_i = s_{k-i+1} $。例如，$ [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} $。 总共有 $ 2^{n-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} $。 **输入输出格式**： **输入格式**： 每个测试包含多个测试用例。第一行包含一个整数 $ 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的序列只有一种划分方式，即它本身，显然是平衡的。 对于第二个测试用例，有两种划分方式： - 序列