← 返回题目列表

AtCoder · agc054_b

B. 贪心除法

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

分数: 800 点

问题陈述

我们有 N 橙子,已编号 1 通过 N。 橙子的重量 i is W_i。 高桥和青木将分享这些橙子如下。

  • 选择一个排列 (p_1, p_2, \cdots, p_N) of (1,2,\cdots,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)。 如果 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