CF1738E.Balance Addicts

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 \lt i_2 \lt \dots \lt 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]$.

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.

• $k \neq k'$,
• $i_j \neq i'_j$ for some 1 \leq j \leq \min\left{ k, k' \right}.

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_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 \lt i_2 \lt \dots \lt i_k \leq n$，满足：

1. $k$ 表示该划分中非空连续子序列的个数；
2. 对每个 $1 \leq j \leq k$，第 $j$ 个连续子序列起始于 $a_{i_j}$，并恰好终止于 $a_{i_{j+1}-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}.$$

例如，序列 $[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'$，
• 存在某个 $1 \leq j \leq \min\left\{ k, k' \right\}$，使得 $i_j \neq i'_j$。

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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output the number of partitions with respect to which the sum of elements in each subsequence is balanced, modulo $998244353$.

对于每个测试用例，输出满足每段子序列元素和均相等的划分方案数，对 $998244353$ 取模。

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}$.

对于第一个测试用例，长度为 $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}$。