Codeforces Global Round 22 |
---|
Finished |
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
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.
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$$$.
61100000000021 140 0 1 051 2 3 2 151 3 5 7 9320 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 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:
For the third test case, there are $$$3$$$ ways to partition it:
For the fourth test case, there are $$$4$$$ ways to partition it:
For the fifth test case, there are $$$2$$$ ways to partition it:
For the sixth test case, every possible partition should be counted. So the answer is $$$2^{32-1} \equiv 150994942 \pmod {998244353}$$$.
Name |
---|