← 返回题目列表

AtCoder · awc0038_d

D. 团队选择总权重

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

分数: 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