概要

各社員の貢献度に比例してボーナスが分配され、全社員が受け取るボーナスの積を既約分数で求め、その分子×分母の逆元を \(\bmod 998244353\) で出力する問題。

考察

まず、社員 \(i\) が \(D\) ヶ月で受け取るボーナスの総額 \(T_i\) は次のように表せる：

\[ T_i = \frac{P_i}{S} \times \sum_{j=1}^{D} W_j = \frac{P_i \cdot W_{\text{total}}}{S} \]

ここで \(W_{\text{total}} = \sum_{j=1}^{D} W_j\) とする。

そして、全社員のボーナスの積 \(R\) は：

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

この式を見ると、\(R\) は分子と分母に分けて扱うことができることが分かる。

素朴な方法では？

そのまま分数同士を掛け算していくと、非常に大きな数になりオーバーフローするし、精度も保てない。 また、毎回 gcd を使って約分しても、計算量的に厳しい。

解決策

最終的な形が分かっているので、直接その形で計算を行う： - 分子：\(\left(\prod_{i=1}^{N} P_i\right) \cdot W_{\text{total}}^N\) - 分母：\(S^N\)

これらをすべて \(\bmod 998244353\) で計算し、最後に分子 × 分母の逆元を計算すれば良い。

さらに重要な点として、\(W_{\text{total}} = 0\) の場合は \(R = 0\) となるため、即座に 0 を出力してよい。

アルゴリズム

1. 各入力を読み込み、\(S = \sum P_i\)、\(W_{\text{total}} = \sum W_j\) を計算する。
2. もし \(W_{\text{total}} = 0\) なら答えは 0。
3. そうでなければ：
   • \(\text{numerator} = \left(\prod P_i\right) \cdot W_{\text{total}}^N \bmod MOD\)
   • \(\text{denominator} = S^N \bmod MOD\)
4. 最後に \((\text{numerator}) \cdot (\text{denominator})^{-1} \bmod MOD\) を出力。

ここで、\((\text{denominator})^{-1} \bmod MOD\) はフェルマーの小定理より \(denominator^{MOD - 2} \bmod MOD\) で求められる。

計算量

• 時間計算量: \(O(N + D + \log MOD)\)
  • \(P\) の積を取るのに \(O(N)\)
  • 累乗は \(O(\log MOD)\)
• 空間計算量: \(O(N + D)\) （入力配列分）

実装のポイント

• 入力を高速に読み込む必要があるため sys.stdin.read を使用している。

• 大きな数の掛け算や累乗はすべて \(\bmod 998244353\) を取りながら行う。

• 特に \(W_{\text{total}} = 0\) の場合を忘れずに処理する。

• モジュラ逆元は Python の組み込み関数 pow(base, exp, mod) を使うのが効率的。

  ソースコード

MOD = 998244353

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

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    D = int(data[1])
    
    P = list(map(int, data[2:2+N]))
    W = list(map(int, data[2+N:2+N+D]))
    
    S = sum(P)
    total_W = sum(W)
    
    if total_W == 0:
        # R = 0
        print(0)
        return
    
    # 分子 A = product of (P[i] * total_W) for all i
    # Denominator B = S^N
    # So R = (P[0]*total_W)*(P[1]*total_W)*...*(P[N-1]*total_W) / S^N
    #     = total_W^N * product(P[i]) / S^N
    
    numerator = 1
    denominator = 1
    
    # Calculate product of P[i]
    prod_P = 1
    for p in P:
        prod_P = (prod_P * p) % MOD
    numerator = (numerator * prod_P) % MOD
    
    # Multiply by total_W^N
    numerator = (numerator * pow(total_W, N, MOD)) % MOD
    
    # Denominator is S^N
    denominator = pow(S, N, MOD)
    
    # Compute numerator * denominator^(-1) mod MOD
    result = (numerator * modinv(denominator, MOD)) % MOD
    print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。