概要

\(N\)人の社員の貢献度に基づいて\(D\)ヶ月間ボーナスを分配し、全社員のボーナス総額の積を\(998244353\)で割った余りを求める問題です。

考察

問題の式を整理すると、社員\(i\)が受け取るボーナス総額は\(T_i = \frac{P_i}{S} \times W_{total}\)（\(W_{total} = \sum_{j=1}^{D} W_j\)）となります。したがって、求める積\(R\)は：

\[R = \prod_{i=1}^{N} T_i = \prod_{i=1}^{N} \left( \frac{P_i \times W_{total}}{S} \right) = \frac{\left( \prod_{i=1}^{N} P_i \right) \times (W_{total})^N}{S^N}\]

となります。この式を既約分数\(\frac{A}{B}\)で表したときの\(A \times B^{-1} \mod 998244353\)を計算すればよいことが分かります。

素朴に実装すると、分子と分母をそれぞれ計算する際に\(N\)回の乗算が必要ですが、\(N\)が最大\(10^6\)であるため、モジュラ演算を適切に行うことで効率的に計算できます。

アルゴリズム

1. 全貢献度の合計\(S\)と全ボーナス原資の合計\(W_{total}\)を計算
2. 分子を\(\prod_{i=1}^{N} (P_i \times W_{total}) \mod 998244353\)として計算
3. 分母を\(S^N \mod 998244353\)として計算
4. 分子に分母のモジュラ逆元を乗算し、結果を\(998244353\)で割った余りを出力

計算量

• 時間計算量: \(O(N + D)\)
  • 入力読み込みと合計計算に\(O(N + D)\)
  • 乗算とべき乗計算に\(O(N + \log MOD)\)
• 空間計算量: \(O(N + D)\)
  • 入力データの保持に必要なメモリ

実装のポイント

• 大きな数値の乗算ではオーバーフローを防ぐため、適宜モジュラ演算を行う

• 分母のべき乗計算には高速べき乗法（バイナリ法）を使用

• 入力データが大きいため、sys.stdin.read()で一括読み込みすると効率的

• 制約条件から\(S\)は\(998244353\)の倍数ではないことが保証されているため、逆元計算が可能

  ソースコード

MOD = 998244353

def main():
    import sys
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); D = int(next(it))
    P_list = [int(next(it)) for _ in range(N)]
    W_list = [int(next(it)) for _ in range(D)]
    
    total_S = sum(P_list)
    total_W = sum(W_list)
    
    S_mod = total_S % MOD
    inv_S_mod = pow(S_mod, MOD-2, MOD)
    
    numerator = 1
    denominator = 1
    for p in P_list:
        term = p * total_W
        numerator = numerator * term % MOD
        denominator = denominator * total_S % MOD
    
    R_mod = numerator * pow(denominator, MOD-2, MOD) % MOD
    print(R_mod)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。