← 返回题目列表

AtCoder · arc214_c

C. 分成 4 队

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

分数: 600 点

问题陈述

有 N 人数 1, \dots ,N。的 实力 人的 人的 i is P_i.

每个人被分配到其中一个团队 A,B,C,D 组成四队。有 4^N 组建团队的方式;其中,找到数字,模 998244353,满足以下所有条件的地层。

  • 各队 A,B,C,D 至少有一个人。
  • 团队成员的力量总和 A 等于团队中人员的力量总和 B.
  • 团队成员的力量总和 C 等于团队中人员的力量总和 D.

约束

  • 4 \le N \le 500
  • 1 \le P_i
  • \sum_{1 \le i \le N} P_i \le 10^5
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

输出数字,模数 998244353,满足问题陈述中的条件的编队。


示例输入 1

4
1 1 2 2

示例输出 1

8

以下八个队形满足条件。

人 1 人 2 人 3 人 4
编队 1 A B C D
编队 2 B A C D
编队 3 A B D C
编队 4 B A D C
编队 5 C D A B
编队 6 C D B A
编队 7 D C A B
编队 8 D C B A

示例输入 2

9
1 2 3 4 5 6 7 8 9

示例输出 2

0

没有满足条件的地层。


示例输入 3

24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

示例输出 3

289359125