Overview

Given \(N\) players, consider all ways to select \(\lfloor N/2 \rfloor + 1\) or more players. For each selection, compute the sum of the selected players’ skill values (score), then output the total of all these scores modulo \(998244353\).

Analysis

Naive Approach and Its Issues

If we try to enumerate all valid selections and compute their scores, the number of subsets can be up to \(2^N\) (\(N \leq 5 \times 10^5\)), which is far too large to handle.

Key Insight: Swapping the Order of Summation (Contribution Decomposition)

The desired value can be written as:

\[\text{Answer} = \sum_{\text{valid selection } S} \sum_{i \in S} W_i\]

Here, we swap the order of summation. Instead of “computing the score for each selection and summing them up,” we think about “how much each player \(i\) contributes to the total”:

\[\text{Answer} = \sum_{i=1}^{N} W_i \times (\text{number of valid selections that include player } i)\]

Computing Each Player’s Contribution

If we fix player \(i\) as always selected, we need to choose some additional players from the remaining \(N-1\) so that the total number of selected players is at least \(\lfloor N/2 \rfloor + 1\). When selecting \(k\) players in total, we choose \(k-1\) players from \(N-1\) players (excluding player \(i\)):

\[\text{(number of valid selections including player } i\text{)} = \sum_{k=\lfloor N/2 \rfloor + 1}^{N} \binom{N-1}{k-1} = \sum_{j=\lfloor N/2 \rfloor}^{N-1} \binom{N-1}{j}\]

This value is the same for all players (it does not depend on \(W_i\)). Therefore:

\[\text{Answer} = \left( \sum_{i=1}^{N} W_i \right) \times \sum_{j=\lfloor N/2 \rfloor}^{N-1} \binom{N-1}{j}\]

Concrete Example (\(N=5\))

The threshold is \(\lfloor 5/2 \rfloor + 1 = 3\) or more players. The number of valid selections including each player is:

\[\sum_{j=2}^{4} \binom{4}{j} = \binom{4}{2} + \binom{4}{3} + \binom{4}{4} = 6 + 4 + 1 = 11\]

The answer is \((W_1 + W_2 + W_3 + W_4 + W_5) \times 11 \mod 998244353\).

Algorithm

1. Compute the total sum \(S = \sum_{i=1}^{N} W_i\).
2. Precompute factorials and their modular inverses so that binomial coefficients \(\binom{n}{r}\) can be computed in \(O(1)\).
3. Compute \(\text{count} = \sum_{j=\lfloor N/2 \rfloor}^{N-1} \binom{N-1}{j}\) using a loop (approximately \(N/2\) iterations).
4. The answer is \(S \times \text{count} \mod 998244353\).

Complexity

• Time complexity: \(O(N)\) (\(O(N)\) for precomputing factorials, \(O(N/2)\) for summing the binomial coefficients)
• Space complexity: \(O(N)\) (factorial table and inverse table)

Implementation Notes

• Computing modular inverses: Since \(998244353\) is prime, by Fermat’s little theorem, the inverse can be computed as \(a^{-1} \equiv a^{p-2} \pmod{p}\). The inverse factorial table can be efficiently computed by first finding the inverse of \(N!\) and then computing backwards.

• Loop range: The loop summing binomial coefficients runs from \(j = \lfloor N/2 \rfloor\) to \(N-1\), which is approximately \(N/2\) iterations, so it is fast enough even for \(N = 5 \times 10^5\).

• The core of this problem is realizing that the contribution is the same for all players. Contribution decomposition (the idea behind linearity of expectation / summation) is a frequently used technique in competitive programming.

  Source Code

import sys

def solve():
    MOD = 998244353
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    W = [int(input_data[i+1]) for i in range(N)]
    
    # We need to sum over all "valid" subsets S (|S| >= floor(N/2)+1) the sum of W_i for i in S.
    # 
    # By linearity of summation, the answer = sum over i of W_i * (number of valid subsets containing i)
    # 
    # For a fixed player i, the number of valid subsets containing i = 
    #   sum_{k = floor(N/2)+1}^{N} C(N-1, k-1)
    # because we fix player i in the subset, then choose k-1 more from the remaining N-1 players.
    # 
    # Let threshold = floor(N/2) + 1
    # count = sum_{k=threshold}^{N} C(N-1, k-1) = sum_{j=threshold-1}^{N-1} C(N-1, j)
    # 
    # This count is the same for every player i.
    # So answer = count * sum(W) mod MOD.
    
    S = sum(W) % MOD
    
    threshold = N // 2 + 1  # minimum team size
    # count = sum_{j = threshold-1}^{N-1} C(N-1, j)
    
    # Precompute factorials and inverse factorials
    max_n = N
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    def comb(n, r):
        if r < 0 or r > n:
            return 0
        return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD
    
    # count = sum_{j = threshold-1}^{N-1} C(N-1, j)
    n1 = N - 1
    lo = threshold - 1  # = floor(N/2)
    
    count = 0
    for j in range(lo, n1 + 1):
        count = (count + comb(n1, j)) % MOD
    
    # But this loop could be up to N/2 iterations which is up to 2.5*10^5, should be fine.
    
    ans = S * count % MOD
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.