/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
みかんが N 個あり，1 から N までの番号がついています． みかん i の重さは W_i です． 高橋くんと青木くんがこれらを以下のようにして分けます．
-
(1,2,\cdots,N) の順列 (p_1, p_2, \cdots, p_N) を選ぶ．
-
i = 1, 2, \cdots, N について，この順に以下のことを行う
- 高橋くんがすでにとったみかんの重さの合計が，青木くんがすでにとったみかんの重さの合計以下なら，みかん p_i を高橋くんがとる． そうでないならみかん p_i を青木くんが取る．
最終的に二人が取るみかんの重さの合計が等しくなるような順列 p が何通りあるかを 998244353 で割った余りを求めてください．
制約
- 2 \leq N \leq 100
- 1 \leq W_i \leq 100
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N W_1 W_2 \cdots W_N
出力
答えを出力せよ．
入力例 1
3 1 1 2
出力例 1
4
条件を満たす p は，(1,3,2),(2,3,1),(3,1,2),(3,2,1) の 4 通りです． 例えば，p=(3,2,1) の時は，以下のように進行します．
- i=1: 高橋くんがすでにとったみかんの重さの合計は 0 で，青木くんがすでにとったみかんの重さの合計は 0 である． 高橋くんがみかん p_i=3 をとる．
- i=2: 高橋くんがすでにとったみかんの重さの合計は 2 で，青木くんがすでにとったみかんの重さの合計は 0 である． 青木くんがみかん p_i=2 をとる．
- i=3: 高橋くんがすでにとったみかんの重さの合計は 2 で，青木くんがすでにとったみかんの重さの合計は 1 である． 青木くんがみかん p_i=1 をとる．
よって p=(3,2,1) は条件を満たす順列です．
入力例 2
4 1 2 3 8
出力例 2
0
入力例 3
20 2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2
出力例 3
373835282
Score : 800 points
Problem Statement
We have N oranges, numbered 1 through N. The weight of Orange i is W_i. Takahashi and Aoki will share these oranges as follows.
-
Choose a permutation (p_1, p_2, \cdots, p_N) of (1,2,\cdots,N).
-
For each i = 1, 2, \cdots, N in this order, do the following.
- If the total weight of the oranges Takahashi has taken is not greater than that of the oranges Aoki has taken, Takahashi takes Orange p_i. Otherwise, Aoki takes Orange p_i.
Find the number of permutations p modulo 998244353 such that the total weight of the oranges Takahashi will take is equal to that of the oranges Aoki will take.
Constraints
- 2 \leq N \leq 100
- 1 \leq W_i \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W_1 W_2 \cdots W_N
Output
Print the answer.
Sample Input 1
3 1 1 2
Sample Output 1
4
There are four permutations p satisfying the condition: (1,3,2),(2,3,1),(3,1,2),(3,2,1). If p=(3,2,1), for example, the following will happen.
- i=1: the total weights of the oranges Takahashi and Aoki have taken are 0 and 0, respectively. Takahashi takes Orange p_i=3.
- i=2: the total weights of the oranges Takahashi and Aoki have taken are 2 and 0, respectively. Aoki takes Orange p_i=2.
- i=3: the total weights of the oranges Takahashi and Aoki have taken are 2 and 1, respectively. Aoki takes Orange p_i=1.
Thus, the permutation p=(3,2,1) counts.
Sample Input 2
4 1 2 3 8
Sample Output 2
0
Sample Input 3
20 2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2
Sample Output 3
373835282