Overview

For all subsets (teams) with \(\lfloor N/2 \rfloor + 1\) or more members, we sum up the total of selected skill values (scores) across all such subsets, and find the result modulo \(998244353\).

Analysis

Key Insight: Counting the Contribution of Each Player (Linearity)

The quantity we want to compute is: - The score \(\sum_{i \in S} W_i\) for each valid selection \(S\) (subset) - Summed over all valid \(S\)

So it becomes: [ \sum{\text{valid } S}\ \sum{i\in S} Wi ] By swapping the order of summation: [ \sum{i=1}^{N} W_i \cdot (\text{number of valid selections that include player }i) ] In other words, if we can determine “how many valid selections include player \(i\)”, we can compute the entire answer.

Symmetry: The Count is the Same Regardless of the Player

Since the condition depends only on “the number of selected people”, for any player \(i\): - “The number of valid selections that include \(i\)” is the same

Therefore, there is no need to count separately for each \(i\), and the answer simplifies to: [ (\sum_i W_i)\times \text{count} ] where count is the number of valid patterns when a specific fixed player is always selected.

Why a Brute-Force Approach is Infeasible

Enumerating all \(2^N\) subsets is impossible when \(N \le 5\times 10^5\).

How to Count: Fix One Player and Choose from the Rest

Suppose we always select a certain player \(i\). There are \(N-1\) remaining people (let \(n=N-1\)), and if we choose \(s\) of them, the total team size is \(1+s\).

Validity condition: [ 1+s \ge \left\lfloor \frac{N}{2} \right\rfloor + 1 \quad\Longleftrightarrow\quad s \ge \left\lfloor \frac{N}{2} \right\rfloor ]

Therefore, count is: [ \sum_{s=\lfloor N/2\rfloor}^{n} \binom{n}{s} ]

Example: When \(N=5\), valid teams have 3 or more members. With one fixed player, we need to choose 2 or more from the remaining 4: [ \binom{4}{2}+\binom{4}{3}+\binom{4}{4}=6+4+1=11 ] Thus, the answer is \((W_1+\cdots+W_5)\times 11\).

Algorithm

1. Compute \(sumW = \sum_{i=1}^{N} W_i \bmod MOD\)
2. Set \(n=N-1\) (the number of people excluding the fixed player)
3. To compute binomial coefficients efficiently, precompute factorials \(fact[k]=k!\) and inverse factorials \(invfact[k]=(k!)^{-1}\) for \(k=0..N\)
   • Since MOD is prime, the modular inverse can be computed using Fermat’s little theorem: \(a^{-1}\equiv a^{MOD-2}\)
   • \(\binom{n}{r}=fact[n]\cdot invfact[r]\cdot invfact[n-r] \bmod MOD\)
4. We can directly compute count as \(\sum_{s=\lfloor N/2\rfloor}^{n}\binom{n}{s}\), but in the code we use the following: [ \sum{s=\lfloor N/2\rfloor}^{n}\binom{n}{s} = 2^n - \sum{s=0}^{\lfloor N/2\rfloor-1}\binom{n}{s} ]
   • \(2^n\) is the total number of ways to choose from the remaining \(n\) people
   • We subtract the cases where the team size is insufficient
5. Final answer: [ ans = sumW \times count \bmod MOD ]

Complexity

• Time complexity: \(O(N)\) (Precomputation of factorials and inverse factorials is \(O(N)\), and the sum of binomial coefficients is roughly \(O(N/2)\))
• Space complexity: \(O(N)\) (\(fact, invfact\) arrays)

Implementation Notes

• Since \(MOD=998244353\) is prime, modular inverse can be computed using pow(x, MOD-2, MOD).

• Since count takes the form 2^n - prefix, we adjust with %(MOD) to avoid negative values.

• To handle small cases like \(N=1\) without issues, when \(\lfloor N/2\rfloor-1\) is negative (i.e., m=-1 in the code), we skip adding to the prefix sum.

  Source Code

import sys

MOD = 998244353
input = sys.stdin.readline

N = int(input())
W = list(map(int, input().split()))
sumW = sum(W) % MOD

n = N - 1  # choose from remaining players when one fixed player is included

# factorials up to N
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD

invfact = [1] * (N + 1)
invfact[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD

def comb(nn, rr):
    if rr < 0 or rr > nn:
        return 0
    return fact[nn] * invfact[rr] % MOD * invfact[nn - rr] % MOD

# threshold: subset size >= floor(N/2)+1
# with fixed element included, choose s >= (floor(N/2)+1)-1 = floor(N/2) from n elements
# count = sum_{s=floor(N/2)}^{n} C(n,s) = 2^n - sum_{s=0}^{floor(N/2)-1} C(n,s)
m = N // 2 - 1  # upper index for excluded prefix: floor(N/2)-1

prefix = 0
if m >= 0:
    if m > n:
        m = n
    for r in range(m + 1):
        prefix += comb(n, r)
        if prefix >= MOD:
            prefix -= MOD

count = (pow(2, n, MOD) - prefix) % MOD
ans = sumW * count % MOD
print(ans)

---

This editorial was generated by gpt-5.2-high.