実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
N 個の整数が与えられます。i 個目の整数は a_i です。 与えられたすべての整数を赤、緑、青の 3 色のいずれかで塗り、以下の条件を満たすようにする方法の個数を 998244353 で割ったあまりを求めてください。
- 赤、緑、青で塗られた整数の総和をそれぞれ R,G,B とする。三辺の長さがそれぞれ R,G,B であるような正の面積の三角形が存在する。
制約
- 3 \leq N \leq 300
- 1 \leq a_i \leq 300(1\leq i\leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N a_1 : a_N
出力
与えられたすべての整数を赤、緑、青の 3 色のいずれかで塗り、条件を満たすようにする方法の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
4 1 1 1 2
出力例 1
18
三角形の三辺の長さがそれぞれ 1,2,2 となるように整数を塗り分けるしかなく、そのような塗り分け方は 18 通り存在します。
入力例 2
6 1 3 2 3 5 2
出力例 2
150
入力例 3
20 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
出力例 3
563038556
Score : 600 points
Problem Statement
You are given N integers. The i-th integer is a_i. Find the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the following condition is satisfied:
- Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.
Constraints
- 3 \leq N \leq 300
- 1 \leq a_i \leq 300(1\leq i\leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 : a_N
Output
Print the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the condition is satisfied.
Sample Input 1
4 1 1 1 2
Sample Output 1
18
We can only paint the integers so that the lengths of the sides of the triangle will be 1, 2 and 2, and there are 18 such ways.
Sample Input 2
6 1 3 2 3 5 2
Sample Output 2
150
Sample Input 3
20 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
Sample Output 3
563038556