Overview

Given \(N\) players, we consider all “valid selections” that choose \(\lfloor N/2 \rfloor + 1\) or more players. For each valid selection, we compute the sum of the selected players’ skill values, and we need to find the total of these sums modulo \(998244353\).

Analysis

Contribution Technique (Considering Each Element’s Contribution)

We transform the problem of “summing the scores over all selections” into the perspective of “for each player \(i\), how many valid selections include them.” Let \(C_i\) denote the number of valid selections that include player \(i\). Then the answer is: $\(\sum_{i=1}^N (W_i \times C_i) \pmod{998244353}\)$

Here, the condition for a valid selection depends only on “the number of selected players.” Therefore, for any player \(i\), the number of valid selections containing them, \(C_i\), is the same value. Denoting this as \(C\), the answer simplifies further: $\(\text{Ans} = \left( \sum_{i=1}^N W_i \right) \times C \pmod{998244353}\)$

Computing \(C\)

Fix player \(i\), and consider how many of the remaining \(N-1\) players need to be selected to form a “valid selection.” Let the minimum selection size be \(K = \lfloor N/2 \rfloor + 1\). To select a total of \(k\) players (\(K \leq k \leq N\)) including player \(i\), we need to choose \(k-1\) players from the remaining \(N-1\). Therefore, \(C\) is expressed as the following sum of binomial coefficients: $\(C = \sum_{k=K}^{N} \binom{N-1}{k-1}\)\( Setting \)m = N-1\( and substituting \)j = k-1\(: \)\(C = \sum_{j=K-1}^{m} \binom{m}{j}\)\( We compute this sum by considering the parity of \)N$.

1. When \(N\) is even

Let \(N = 2p\), so \(K = p+1\). \(C = \binom{2p-1}{p} + \binom{2p-1}{p+1} + \dots + \binom{2p-1}{2p-1}\). We use the property \(\sum_{j=0}^m \binom{m}{j} = 2^m\) and the symmetry \(\binom{m}{j} = \binom{m}{m-j}\). Since \(m = 2p-1\) is odd, splitting all \(2p\) terms in half: $\(\sum_{j=0}^{p-1} \binom{2p-1}{j} = \sum_{j=p}^{2p-1} \binom{2p-1}{j}\)\( This shows each half is exactly half of the total. Therefore, \)C = 2^{m} \div 2 = 2^{m-1} = 2^{N-2}$.

2. When \(N\) is odd

Let \(N = 2p+1\), so \(K = p+1\). \(C = \binom{2p}{p} + \binom{2p}{p+1} + \dots + \binom{2p}{2p}\). Since \(m = 2p\) is even, the middle term \(\binom{2p}{p}\) exists. $\(2^m = \sum_{j=0}^{p-1} \binom{2p}{j} + \binom{2p}{p} + \sum_{j=p+1}^{2p} \binom{2p}{j}\)\( By symmetry, \)\sum{j=0}^{p-1} \binom{2p}{j} = \sum{j=p+1}^{2p} \binom{2p}{j}\(, so letting this sum be \)S\(: \)2^m = 2S + \binom{2p}{p} \implies S = \frac{2^m - \binom{2p}{p}}{2}\( The desired \)C\( is \)C = \binom{2p}{p} + S\(, so: \)\(C = \binom{2p}{p} + \frac{2^m - \binom{2p}{p}}{2} = \frac{2^m + \binom{2p}{p}}{2}\)$

Algorithm

1. Compute the total sum \(W_{sum}\) of \(W_i\).
2. If \(N\) is even:
   • \(C = 2^{N-2} \pmod{MOD}\)
3. If \(N\) is odd:
   • Set \(m = N-1, p = m/2\).
   • Compute the binomial coefficient \(\binom{m}{p}\).
   • \(C = (2^m + \binom{m}{p}) \times 2^{-1} \pmod{MOD}\)
4. Output \(W_{sum} \times C \pmod{MOD}\).

Complexity

• Time complexity: \(O(N)\)
  • Computing the sum of \(W_i\) and, when \(N\) is odd, computing \(\binom{m}{p}\) each take \(O(N)\).
• Space complexity: \(O(N)\)
  • Memory is needed to store the input values.

Implementation Notes

• Modular arithmetic with large numbers: Take the remainder modulo \(998244353\) at each step during computation.

• Modular inverse: For computing \(\frac{1}{2}\) and the denominator in \(\binom{m}{p}\), use modular inverse via Fermat’s little theorem (pow(a, MOD - 2, MOD)).

• Fast input: Since \(N\) can be large, in Python using sys.stdin.read().split() or similar methods allows for faster processing.

  Source Code

import sys

# 競技プログラミングのエキスパートとして、効率的かつ正確な解法を実装します。
# 選手の人数 N と各選手の実力値 W_i が与えられたとき、
# 有効な選び方（選ばれた人数 k >= floor(N/2) + 1）のスコア合計を求めます。
#
# 各選手 i について、その選手が含まれる有効な選び方の個数 C を求めれば、
# 答えは (sum(W_i) * C) % 998244353 となります。
# 人数条件は全選手に対して対称であるため、C は選手によらず一定です。

def solve():
    # 標準入力から全てのデータを読み込み、スペース区切りで分割します。
    # 大規模な入力に対して sys.stdin.read().split() は Python で高速な手法の一つです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 選手数 N と実力値の合計 W_sum を計算します。
    N = int(input_data[0])
    MOD = 998244353
    
    W_sum = 0
    # スライスを使わずにループで加算することで、メモリ消費を抑えつつ合計を求めます。
    for i in range(1, N + 1):
        W_sum = (W_sum + int(input_data[i])) % MOD
        
    # 各選手が含まれる有効な選び方の数 C を計算します。
    # 有効な選び方の人数を k とすると、k >= K = floor(N/2) + 1 です。
    # 特定の選手が含まれる有効な選び方の数は、残りの N-1 人から k-1 人を選ぶ組み合わせの和です。
    # C = sum_{k=K}^{N} comb(N-1, k-1)
    
    if N % 2 == 0:
        # N が偶数の場合:
        # K = N/2 + 1, m = N-1 とおくと、
        # C = sum_{i=N/2}^{N-1} comb(N-1, i)
        # 二項係数の対称性 comb(m, i) = comb(m, m-i) により、
        # この和は全組み合わせの半分 2^(N-1) / 2 = 2^(N-2) になります。
        if N < 2: # 制約により N >= 1 ですが念のため
            C = 1 if N == 1 else 0
        else:
            C = pow(2, N - 2, MOD)
    else:
        # N が奇数の場合:
        # N = 2p + 1 とおくと、K = p + 1, m = N-1 = 2p となります。
        # C = sum_{i=p}^{2p} comb(2p, i)
        # 全和 2^(2p) = sum_{i=0}^{p-1} comb(2p, i) + comb(2p, p) + sum_{i=p+1}^{2p} comb(2p, i)
        # 対称性より、sum_{i=0}^{p-1} comb(2p, i) = sum_{i=p+1}^{2p} comb(2p, i)
        # よって C = comb(2p, p) + (2^(2p) - comb(2p, p)) / 2 = (2^(2p) + comb(2p, p)) / 2
        m = N - 1
        p = m // 2
        
        # 二項係数 comb(m, p) を O(N) で計算します。
        num = 1
        den = 1
        for i in range(p):
            num = (num * (m - i)) % MOD
            den = (den * (i + 1)) % MOD
        
        # 逆元を用いて comb(m, p) % MOD を求めます。
        comb = (num * pow(den, MOD - 2, MOD)) % MOD
        inv2 = pow(2, MOD - 2, MOD)
        C = (pow(2, m, MOD) + comb) * inv2 % MOD
        
    # 全ての有効な選び方のスコア合計を出力します。
    print((W_sum * C) % MOD)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.