Codeforces Global Round 26 |
---|
Finished |
The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.
You are given an array $$$a$$$ of length $$$n$$$. Start with $$$c = 0$$$. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$ (in increasing order) do exactly one of the following:
Let the maximum final value of $$$c$$$ after the procedure described above be equal to $$$k$$$. Find the number of unique procedures that result in $$$c = k$$$. Two procedures are different if at any index $$$i$$$, one procedure chose option $$$1$$$ and another chose option $$$2$$$, even if the value of $$$c$$$ is equal for both procedures after that turn.
Since the answer may be large, output it modulo $$$998\,244\,353$$$.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).
The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output a single integer — the number of unique procedures that result in $$$c = k$$$, modulo $$$998\,244\,353$$$.
542 -5 3 -381 4 3 4 1 4 3 43-1 -2 -34-1000000000 1000000000 1000000000 100000000041 9 8 4
12 256 1 8 16
In the first test case, it can be shown that our maximal final value of $$$c$$$ is $$$3$$$. There are $$$12$$$ ways to achieve this because in order to get $$$3$$$, we have to take absolute value at indices $$$2$$$ or $$$4$$$, or both, resulting in $$$3$$$ ways. For the other two indices, it doesn't change the value whether we take absolute value or not, so we have $$$2 \cdot 2 = 4$$$ ways for them. In total, we have $$$3 \cdot 4 = 12$$$ ways.
In the second test case, taking the absolute value will never change anything, so we can either take absolute value or not, for every index. This gives us $$$2^8 = 256$$$ possible ways.
Name |
---|