/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 人の選手が所属するスポーツクラブの監督です。選手には 1 から 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
- 1 行目には、選手の人数を表す整数 N が与えられる。
- 2 行目には、各選手の実力値を表す N 個の整数 W_1, W_2, \ldots, W_N がスペース区切りで与えられる。
出力
全ての有効な選び方のスコアを足し合わせた値を 998244353 で割った余りを 1 行で出力せよ。
入力例 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
Score : 400 pts
Problem Statement
Takahashi is the coach of a sports club with N players. The players are numbered from 1 to N, and players with different numbers are considered distinct. The skill value of player i (1 \leq i \leq N) is an integer W_i.
Takahashi is going to form a team from the N players. For each player, he decides exactly once whether to "select" or "not select" them (the same player cannot be selected multiple times). Including the case where no one is selected, there are 2^N possible ways to form a team.
Let \lfloor x \rfloor denote the largest integer not exceeding x. Among the 2^N possible selections, those where the number of selected players is at least \lfloor N/2 \rfloor + 1 are called valid selections. For example, when N = 5, at least 3 players must be selected, and when N = 6, at least 4 players must be selected.
For each valid selection, the score is defined as the sum of the skill values of the selected players. For all valid selections, compute each score and find the total sum of all these scores. If different selections have the same score, each is counted separately in the sum.
Since the answer can be very large, output the remainder when divided by 998244353.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq W_i \leq 10^9
- All inputs are integers.
Input
N W_1 W_2 \ldots W_N
- The first line contains an integer N, representing the number of players.
- The second line contains N integers W_1, W_2, \ldots, W_N separated by spaces, representing the skill values of each player.
Output
Output in one line the remainder when the total sum of scores over all valid selections is divided by 998244353.
Sample Input 1
3 1 2 3
Sample Output 1
18
Sample Input 2
4 1 2 3 4
Sample Output 2
40
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10
Sample Output 3
14080
Sample Input 4
20 15 92 65 35 89 79 32 38 46 26 43 38 32 79 50 28 84 19 71 69
Sample Output 4
270008320
Sample Input 5
1 1000000000
Sample Output 5
1755647