概要

\(N\) 人の選手から \(\lfloor N/2 \rfloor + 1\) 人以上を選ぶ「有効な選び方」すべてについて、選ばれた選手の実力値の合計を求め、その総和を \(998244353\) で割った余りを求める問題です。

考察

主客転倒（各要素の貢献度を考える）

「すべての選び方のスコアを足す」という問題を、「各選手 \(i\) が、何通りの有効な選び方に含まれるか」という視点に切り替えて考えます。 選手 \(i\) が含まれる有効な選び方の数を \(C_i\) とすると、求める答えは次のようになります。 $\(\sum_{i=1}^N (W_i \times C_i) \pmod{998244353}\)$

ここで、有効な選び方の条件は「選ばれた人数」のみに依存しています。したがって、どの選手 \(i\) についても、その選手が含まれる有効な選び方の数 \(C_i\) はすべて同じ値になります。これを \(C\) とおくと、答えはさらに簡略化できます。 $\(\text{Ans} = \left( \sum_{i=1}^N W_i \right) \times C \pmod{998244353}\)$

\(C\) の計算

選手 \(i\) を固定したとき、残りの \(N-1\) 人から何人選べば「有効な選び方」になるかを考えます。 選ぶ人数の下限を \(K = \lfloor N/2 \rfloor + 1\) とすると、選手 \(i\) を含めて全体で \(k\) 人（\(K \leq k \leq N\)）選ぶためには、残りの \(N-1\) 人から \(k-1\) 人選ぶ必要があります。 したがって、\(C\) は以下の二項係数の和で表されます。 $\(C = \sum_{k=K}^{N} \binom{N-1}{k-1}\)\( \)m = N-1\( とおき、添字を \)j = k-1\( と置換すると、 \)\(C = \sum_{j=K-1}^{m} \binom{m}{j}\)\( となります。この和を \)N$ の奇偶で分けて計算します。

1. \(N\) が偶数のとき

\(N = 2p\) とすると、\(K = p+1\) です。 \(C = \binom{2p-1}{p} + \binom{2p-1}{p+1} + \dots + \binom{2p-1}{2p-1}\) となります。 二項係数の性質 \(\sum_{j=0}^m \binom{m}{j} = 2^m\) と、対称性 \(\binom{m}{j} = \binom{m}{m-j}\) を利用します。 \(m = 2p-1\) は奇数なので、全 \(2p\) 個の項を半分に分けると： $\(\sum_{j=0}^{p-1} \binom{2p-1}{j} = \sum_{j=p}^{2p-1} \binom{2p-1}{j}\)\( となり、全体のちょうど半分であることがわかります。 よって、\)C = 2^{m} \div 2 = 2^{m-1} = 2^{N-2}$ となります。

2. \(N\) が奇数のとき

\(N = 2p+1\) とすると、\(K = p+1\) です。 \(C = \binom{2p}{p} + \binom{2p}{p+1} + \dots + \binom{2p}{2p}\) となります。 \(m = 2p\) は偶数なので、真ん中の項 \(\binom{2p}{p}\) が存在します。 $\(2^m = \sum_{j=0}^{p-1} \binom{2p}{j} + \binom{2p}{p} + \sum_{j=p+1}^{2p} \binom{2p}{j}\)\( 対称性より \)\sum{j=0}^{p-1} \binom{2p}{j} = \sum{j=p+1}^{2p} \binom{2p}{j}\( なので、この和を \)S\( とおくと： \)2^m = 2S + \binom{2p}{p} \implies S = \frac{2^m - \binom{2p}{p}}{2}\( 求めたい \)C\( は \)C = \binom{2p}{p} + S\( なので、 \)\(C = \binom{2p}{p} + \frac{2^m - \binom{2p}{p}}{2} = \frac{2^m + \binom{2p}{p}}{2}\)$ となります。

アルゴリズム

1. \(W_i\) の総和 \(W_{sum}\) を求める。
2. \(N\) が偶数の場合：
   • \(C = 2^{N-2} \pmod{MOD}\)
3. \(N\) が奇数の場合：
   • \(m = N-1, p = m/2\) とする。
   • 二項係数 \(\binom{m}{p}\) を求める。
   • \(C = (2^m + \binom{m}{p}) \times 2^{-1} \pmod{MOD}\)
4. \(W_{sum} \times C \pmod{MOD}\) を出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(W_i\) の合計、および \(N\) が奇数の場合の \(\binom{m}{p}\) の計算に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 入力値を保持するためのメモリが必要です。

実装のポイント

• 大きな数の余り: 計算の途中で随時 \(998244353\) で割った余りを取ります。

• 逆元: \(\frac{1}{2}\) の計算や \(\binom{m}{p}\) の分母の計算には、フェルマーの小定理を用いた逆元（pow(a, MOD - 2, MOD)）を利用します。

• 高速な入力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを用いると高速に処理できます。

  ソースコード

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()

---

この解説は gemini-3-flash-thinking によって生成されました。