CF1738E Balance Addicts

给定一个长度为 $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]$ 不是。 形式化地，每一种划分可以用一个下标序列 $i_1, i_2, \dots, i_k$（长度为 $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}-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$ 表示对应划分下每个子序列的元素和。形式化地，对于每个 $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$。

每组测试数据包含多个测试用例。第一行包含一个整数 $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$ 的序列只有一种划分方式，即它本身，显然是平衡的。 对于第二个测试用例，有 $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}$。 由 ChatGPT 4.1 翻译