分数: 400 分
问题陈述
高桥是一家体育俱乐部的教练 N 玩家。球员编号从 1 to N,并且具有不同号码的玩家被认为是不同的。玩家的技能值 i (1 \leq i \leq N) 是一个整数 W_i.
高桥将组建一支来自 N 玩家。对于每个玩家,他只决定一次是否“选择”或“不选择”他们(同一玩家不能被多次选择)。包括无人选中的情况,还有 2^N 组建团队的可能方法。
让 \lfloor x \rfloor 表示不超过的最大整数 x。其中 2^N 可能的选择,选择的玩家数量至少为 \lfloor N/2 \rfloor + 1 被称为 有效选择。例如,当 N = 5,至少 3 必须选择玩家,并且当 必须选择 N = 6,至少 4 玩家。
对于每个有效选择, 分数 游戏的 被定义为所选玩家的技能值的总和。对于所有有效选择,计算每个分数并找到所有这些分数的总和。如果不同选项得分相同,则分别计入总分。
由于答案可能非常大,因此输出除以的余数 998244353.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq W_i \leq 10^9
- 所有输入均为整数。
输入
N W_1 W_2 \ldots W_N
- 第一行包含一个整数 N,代表玩家数量。
- 第二行包含 N 整数 W_1, W_2, \ldots, W_N 以空格分隔,代表每个玩家的技能值。
输出
在一行中输出所有有效选项的分数总和除以的余数 998244353.
示例输入 1
3 1 2 3
示例输出 1
18
示例输入 2
4 1 2 3 4
示例输出 2
40
示例输入 3
10 1 2 3 4 5 6 7 8 9 10
示例输出 3
14080
示例输入 4
20 15 92 65 35 89 79 32 38 46 26 43 38 32 79 50 28 84 19 71 69
示例输出 4
270008320
示例输入 5
1 1000000000
示例输出 5
1755647