← 返回题目列表

Codeforces · 1783/D

D. 不同的阵列

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

您必须对此数组执行 $$$n-2$$$ 操作序列:

- 在第一次操作期间,您可以将 $$$a_2$$$ 添加到 $$$a_1$$$ 并从 $$$a_3$$$ 中减去 $$$a_2$$$,或者将 $$$a_2$$$ 添加到 $$$a_3$$$ 并从 $$$a_1$$$ 中减去 $$$a_2$$$;
- 在第二次操作期间,您可以将 $$$a_3$$$ 添加到 $$$a_2$$$ 并从 $$$a_4$$$ 中减去 $$$a_3$$$,或者将 $$$a_3$$$ 添加到 $$$a_4$$$ 并从 $$$a_2$$$ 中减去 $$$a_3$$$;
- ...
- 在最后一个操作中,您可以将 $$$a_{n-1}$$$ 添加到 $$$a_{n-2}$$$ 并从 $$$a_n$$$ 中减去 $$$a_{n-1}$$$,或者将 $$$a_{n-1}$$$ 添加到 $$$a_n$$$ 并从 $$$a_{n-1}$$$ 中减去 $$$a_{n-1}$$$ $$$a_{n-2}$$$。

因此,在第 $$$i$$$ 操作期间,将 $$$a_{i+1}$$$ 的值添加到它的一个邻居中,并从另一个邻居中减去它。

例如,如果您有数组 $$$[1, 2, 3, 4, 5]$$$,则可能的操作序列之一是:

- 从 $$$a_3$$$ 中减去 $$$2$$$ 并将其添加到 $$$a_1$$$ 中,因此数组变为 $$$[3, 2, 1, 4, 5]$$$;
- 从 $$$a_2$$$ 中减去 $$$1$$$ 并将其添加到 $$$a_4$$$,因此数组变为 $$$[3, 1, 1, 5, 5]$$$;
- 从 $$$a_3$$$ 中减去 $$$5$$$ 并将其添加到 $$$a_5$$$,因此数组变为 $$$[3, 1, -4, 5, 10]$$$。

因此,结果数组是 $$$[3, 1, -4, 5, 10]$$$。

如果可以通过对 $$$a$$$ 执行上述操作序列来获取数组,则该数组是可达的。您必须计算可到达数组的数量,并以 $$$998244353$$$ 为模打印它。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 300$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 300$$$)。

输出

打印一个整数 — 可到达数组的数量。由于答案可能非常大,因此打印其对 $$$998244353$$$ 取模后的余数。

示例

输入 #1

4
1 1 1 1

输出 #1

3

输入 #2

5
1 2 3 5 0

输出 #2

7