Different Arrays
Contest: Educational Codeforces Round 141 (Rated for Div. 2)
Difficulty rating: 2000
Tags: brute force, dp, implementation

You are given an array $$$a$$$ consisting of $$$n$$$ integers.

You have to perform the sequence of $$$n-2$$$ operations on this array:

- during the first operation, you either add $$$a_2$$$ to $$$a_1$$$ and subtract $$$a_2$$$ from $$$a_3$$$, or add $$$a_2$$$ to $$$a_3$$$ and subtract $$$a_2$$$ from $$$a_1$$$;
- during the second operation, you either add $$$a_3$$$ to $$$a_2$$$ and subtract $$$a_3$$$ from $$$a_4$$$, or add $$$a_3$$$ to $$$a_4$$$ and subtract $$$a_3$$$ from $$$a_2$$$;
- ...
- during the last operation, you either add $$$a_{n-1}$$$ to $$$a_{n-2}$$$ and subtract $$$a_{n-1}$$$ from $$$a_n$$$, or add $$$a_{n-1}$$$ to $$$a_n$$$ and subtract $$$a_{n-1}$$$ from $$$a_{n-2}$$$.

So, during the $$$i$$$-th operation, you add the value of $$$a_{i+1}$$$ to one of its neighbors, and subtract it from the other neighbor.

For example, if you have the array $$$[1, 2, 3, 4, 5]$$$, one of the possible sequences of operations is:

- subtract $$$2$$$ from $$$a_3$$$ and add it to $$$a_1$$$, so the array becomes $$$[3, 2, 1, 4, 5]$$$;
- subtract $$$1$$$ from $$$a_2$$$ and add it to $$$a_4$$$, so the array becomes $$$[3, 1, 1, 5, 5]$$$;
- subtract $$$5$$$ from $$$a_3$$$ and add it to $$$a_5$$$, so the array becomes $$$[3, 1, -4, 5, 10]$$$.

So, the resulting array is $$$[3, 1, -4, 5, 10]$$$.

An array is reachable if it can be obtained by performing the aforementioned sequence of operations on $$$a$$$. You have to calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$3 \le n \le 300$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$).

Output format:
Print one integer — the number of reachable arrays. Since the answer can be very large, print its remainder modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4
1 1 1 1

Example output:
3

Example input:
5
1 2 3 5 0

Example output:
7

Editorial:
One of the key observations to this problem is that, after the first $$$i$$$ operations, the first $$$i$$$ elements of the array are fixed and cannot be changed afterwards. Also, after the $$$i$$$-th operation, the elements on positions from $$$i+3$$$ to $$$n$$$ are the same as they were before applying the operations.
This allows us to write the following dynamic programming: $$$dp_{i, x, y}$$$ — the number of different prefixes our array can have, if we have performed $$$i$$$ operations, the $$$(i+1)$$$-th element is $$$x$$$, and the $$$(i+2)$$$-th element is $$$y$$$. The elements after $$$i+2$$$ are the same as in the original array, and the elements before $$$i+1$$$ won't be changed anymore, so we are interested only in these two elements.
Let's analyze the transitions in this dynamic programming. We apply the operation $$$i+1$$$ to the elements $$$a_{i+1}$$$, $$$a_{i+2}$$$ and $$$a_{i+3}$$$. If we add $$$a_{i+2}$$$ to $$$a_{i+1}$$$, then we subtract it from $$$a_{i+3}$$$, so we transition into state $$$dp_{i+1, y, a_{i+3}-y}$$$. Otherwise, we transition into state $$$dp_{i+1, y, a_{i+3}+y}$$$. The element we leave behind is either $$$x-y$$$ or $$$x+y$$$, and if $$$y \ne 0$$$, these two transitions give us different prefixes. But if $$$y=0$$$, we need to make only one of these transitions, because adding or subtracting $$$0$$$ actually makes no difference.
Okay, now we've got a solution with dynamic programming in $$$O(n^3 A^2)$$$, where $$$n$$$ is up to $$$300$$$ and $$$A$$$ is up to $$$300$$$. This is too slow. But we can notice that the value of $$$a_{i+1}$$$ actually does not affect our transitions at all; we can just discard it, so our dynamic programming becomes $$$O(n^2 A)$$$, which easily fits into TL.
Small implementation note: elements can become negative, and in order to store dynamic programming with negative states in an array, we need to do something about that. I don't recommend using maps (neither ordered nor unordered): you either get an extra log factor, or make your solution susceptible to hacking. Instead, let's say that the value of $$$dp_{i, y}$$$, where $$$y$$$ can be a negative number, will be stored as $$$dp[i][y + M]$$$ in the array, where $$$M$$$ is some constant which is greater than the maximum possible $$$|y|$$$ (for example, $$$10^5$$$ in this problem). That way, all array indices will be non-negative.
Solution complexity: $$$O(n^2 A)$$$.