Divide into 4 TeamsAI (CI翻译)
Problem Statement
There are $N$ people numbered $1, \dots ,N$. The strength of person $i$ is $P_i$.
Each person is assigned to one of the teams $A,B,C,D$ to form four teams. There are $4^N$ ways to form teams; among these, find the number, modulo $998244353$, of formations that satisfy all of the following conditions.
- Each of the teams
$A,B,C,D$has at least one person. - The sum of the strengths of the people in team
$A$equals the sum of the strengths of the people in team$B$. - The sum of the strengths of the people in team
$C$equals the sum of the strengths of the people in team$D$.
Constraints
$4 \le N \le 500$$1 \le P_i$$\sum_{1 \le i \le N} P_i \le 10^5$- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
P_1 P_2 \ldots P_NOutput
Output the number, modulo $998244353$, of formations that satisfy the conditions in the problem statement.
{"titleZh":"分成 4 个队伍","bodyZh":"## 题目描述\n\n有 $N$ 个人，编号为 $1, \dots ,N$。第 $i$ 个人的实力为 $P_i$。\n\n将每个人分配到队伍 $A,B,C,D$ 中的一个，组成四支队伍。组成队伍的方法共有 $4^N$ 种，请求出其中满足以下所有条件的方法数，结果对 $998244353$ 取模。\n\n- 队伍 $A,B,C,D$ 中的每支队伍都至少有一个人。\n- 队伍 $A$ 中所有人的实力之和等于队伍 $B$ 中所有人的实力之和。\n- 队伍 $C$ 中所有人的实力之和等于队伍 $D$ 中所有人的实力之和。\n\n## 约束条件\n\n- $4 \le N \le 500$\n- $1 \le P_i$\n- $\sum_{1 \le i \le N} P_i \le 10^5$\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入中按以下格式给出：\n\n\nN\nP_1 P_2 \\ldots P_N\n$998244353$ 取模。"}AI (CI翻译)
样例
4
1 1 2 2
8
9
1 2 3 4 5 6 7 8 9
0
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
289359125
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。