AtCoder Grand Contest 054
翻译中…
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.
翻译中…
样例
Input #1
3
1 1 2
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.
Input #2
4
1 2 3 8
Output #2
0
Input #3
20
2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2
Output #3
373835282
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。