Overview

Given \(N\) players, consider all combinations of selecting \(\lfloor N/2 \rfloor + 1\) or more players. For each combination, compute the sum of the selected players’ skill values (score), and find the total of all these scores modulo \(998244353\).

Analysis

In this problem, we want to find the total score across all “valid selections” (where the number of selected players is at least \(\lfloor N/2 \rfloor + 1\)). A naive approach would be to enumerate all subsets and compute the score only for those satisfying the condition, but there are \(2^N\) combinations, and since \(N\) can be up to \(5 \times 10^5\), this is far too slow.

Instead, we consider how much each player’s skill value \(W_i\) contributes to the final answer. In other words, we count the number of “valid teams” that include player \(i\), and add \(W_i\) multiplied by that count to the answer.

The number of ways to form a team that includes player \(i\) is: “fix player \(i\), and choose \(\lfloor N/2 \rfloor\) or more players from the remaining \(N-1\) players.” This can be computed using combinatorics.

Specifically, when forming a team of \(k\) players total that includes player \(i\), the remaining \(k-1\) players are chosen from \(N-1\) players, so the number of combinations is \(\binom{N-1}{k-1}\). Here, \(k\) ranges from \(\lfloor N/2 \rfloor + 1\) to \(N\).

Therefore, the number of times player \(i\) contributes to the score is:

\[ \sum_{k = \lfloor N/2 \rfloor + 1}^{N} \binom{N-1}{k-1} = \sum_{s = \lfloor N/2 \rfloor}^{N-1} \binom{N-1}{s} \]

By precomputing this cumulative sum, we can determine each player’s contribution count in constant time.

Algorithm

1. First, precompute factorials and their modular inverses to efficiently compute \(\binom{n}{k} \bmod 998244353\).
2. To compute each player’s contribution count, prepare a suffix sum array suff: $\( \text{suff}[s] = \sum_{k=s}^{N-1} \binom{N-1}{k} \)$
3. For each player \(i\), add \(W_i\) multiplied by the contribution count (suff[min_select - 1]) to the answer.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Computing combinations requires modular inverse calculation using Fermat’s little theorem (\(998244353\) is prime).

• Precomputation of inverses can be done efficiently using a DP-like backward computation.

• Always take \(\bmod 998244353\) throughout the computation.

  Source Code

def main():
    MOD = 998244353
    N = int(input())
    W = list(map(int, input().split()))

    # 前計算: 組み合わせ nCk mod MOD
    # fact[i] = i! % MOD
    # ifact[i] = (i!)^{-1} mod MOD
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD

    def modinv(a):
        return pow(a, MOD-2, MOD)

    ifact = [1] * (max_n + 1)
    ifact[max_n] = modinv(fact[max_n])
    for i in range(max_n - 1, -1, -1):
        ifact[i] = ifact[i+1] * (i+1) % MOD

    def comb(n, k):
        if k < 0 or k > n:
            return 0
        return fact[n] * ifact[k] % MOD * ifact[n-k] % MOD

    min_select = N // 2 + 1  # この人数以上選ばなければならない

    total = 0
    # 各選手 i が何回スコアに寄与するかを数える
    # それは、選手 i を含む有効なチームの数に等しい
    # 選手 i を含むチームで、残り N-1 人から size-1 人を選ぶ
    # size は min_select 〜 N
    # つまり sum_{s=min_select-1}^{N-1} C(N-1, s)

    # 事前に累積和を計算しておく
    # suff[s] = sum_{k=s}^{N-1} C(N-1, k)
    suff = [0] * (N + 1)
    tmp = 0
    for s in range(N-1, min_select - 2, -1):
        tmp = (tmp + comb(N-1, s)) % MOD
        suff[s] = tmp

    for i in range(N):
        w = W[i]
        count = suff[min_select - 1]
        total = (total + w * count) % MOD

    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.