CF1783D.Different Arrays
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 a2 to a1 and subtract a2 from a3 , or add a2 to a3 and subtract a2 from a1 ;
- during the second operation, you either add a3 to a2 and subtract a3 from a4 , or add a3 to a4 and subtract a3 from a2 ;
- ...
- during the last operation, you either add an−1 to an−2 and subtract an−1 from an , or add an−1 to an and subtract an−1 from an−2 .
So, during the i -th operation, you add the value of ai+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 a3 and add it to a1 , so the array becomes [3,2,1,4,5] ;
- subtract 1 from a2 and add it to a4 , so the array becomes [3,1,1,5,5] ;
- subtract 5 from a3 and add it to a5 , 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 .
输入格式
The first line contains one integer n ( 3≤n≤300 ).
The second line contains n integers a1,a2,…,an ( 0≤ai≤300 ).
输出格式
Print one integer — the number of reachable arrays. Since the answer can be very large, print its remainder modulo 998244353 .
输入输出样例
输入#1
4 1 1 1 1
输出#1
3
输入#2
5 1 2 3 5 0
输出#2
7