E. Balance Addicts
combinatorics; dp; math; two pointers
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 \(k\) is the number of non-empty continuous subsequences in the partition; 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\}$$$.
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\).
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}\).