概要

この問題は、各社員が \(D\) ヶ月間で受け取るボーナスの総額 \(T_i\) を求め、それら全社員分の積 \(R = \prod_{i=1}^{N} T_i\) を計算する問題です。一見すると複雑な計算が必要に見えますが、数式を整理することで非常にシンプルな形に落とし込むことができます。

考察

1. 数式の整理

まず、社員 \(i\) が \(D\) ヶ月間で受け取るボーナスの総額 \(T_i\) を整理しましょう。 各月 \(j\) に受け取る額は \(\frac{P_i \times W_j}{S}\) です。これを \(j=1\) から \(D\) まで足し合わせると、以下のようになります。

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

ここで、全月のボーナス原資の合計を \(W_{sum} = \sum_{j=1}^{D} W_j\) とおくと、 $\(T_i = \frac{P_i \times W_{sum}}{S}\)$ と簡略化できます。

次に、求めたい全社員のボーナス総額の積 \(R\) を計算します。 $\(R = \prod_{i=1}^{N} T_i = \prod_{i=1}^{N} \left( \frac{P_i \times W_{sum}}{S} \right)\)$

この積を展開すると、共通する係数部分を外に出すことができます。 $\(R = \left( \frac{W_{sum}}{S} \right)^N \times \prod_{i=1}^{N} P_i\)$

2. モジュラ逆元の利用

計算すべき値は \(R = (\prod P_i) \times (W_{sum} \times S^{-1})^N\) です。 制約より \(S\) は \(998244353\) の倍数ではないため、フェルマーの小定理を用いて \(S\) の逆元 \(S^{-1} \pmod{998244353}\) を求めることができます。

アルゴリズム

1. 入力の合計と積の計算:
   • 各社員の貢献度の合計 \(S = \sum P_i \pmod{MOD}\) を計算する。
   • 各月のボーナス原資の合計 \(W_{sum} = \sum W_j \pmod{MOD}\) を計算する。
   • 各社員の貢献度の積 \(P_{prod} = \prod P_i \pmod{MOD}\) を計算する。
2. 逆元の計算:
   • \(S\) のモジュラ逆元 \(S^{-1} \equiv S^{MOD-2} \pmod{MOD}\) を計算する。
3. 累乗の計算:
   • 比率の \(N\) 乗である \((\frac{W_{sum}}{S})^N \equiv (W_{sum} \times S^{-1})^N \pmod{MOD}\) を計算する。
4. 最終回答:
   • \(P_{prod} \times (W_{sum} \times S^{-1})^N \pmod{MOD}\) を出力する。

計算量

• 時間計算量: \(O(N + D + \log N)\)
  • \(P_i\) の合計と積の計算に \(O(N)\)
  • \(W_j\) の合計の計算に \(O(D)\)
  • 繰り返し二乗法による累乗計算に \(O(\log N)\) かかります。
• 空間計算量: \(O(N + D)\)
  • 入力値を保持するための配列に依存します。

実装のポイント

• 高速な入出力: \(N, D\) が最大 \(10^6\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて一括で入力を読み込むのが効率的です。

• 大きな数の計算: Pythonは標準で多倍長整数を扱えますが、計算の途中で逐次 MOD を取ることで、メモリ消費を抑えつつ高速に計算できます。

• 累乗関数: Pythonの pow(a, b, m) は内部で繰り返し二乗法を用いており、非常に高速に \(a^b \pmod m\) を計算できます。

  ソースコード

import sys

def solve():
    """
    The problem asks for the product of all employees' total bonuses.
    
    Each employee i receives a total bonus T_i = (P_i / S) * W_sum,
    where:
    - P_i is the contribution of employee i
    - S = sum(P_1, ..., P_N) is the total contribution
    - W_sum = sum(W_1, ..., W_D) is the total bonus pool over D months
    
    The product R is given by:
    R = product_{i=1 to N} T_i
      = product_{i=1 to N} ((P_i / S) * W_sum)
      = (product_{i=1 to N} P_i) * (W_sum / S)^N
    
    We need to compute R mod 998244353.
    Since 998244353 is a prime and S is not a multiple of 998244353,
    we can use modular arithmetic and modular inverses.
    """
    
    # Set the modulo
    MOD = 998244353
    
    # Use fast I/O to read all data at once
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Parse N (number of employees) and D (number of months)
    N = int(input_data[0])
    D = int(input_data[1])
    
    # Parse P (contributions) and W (monthly bonus pools)
    # map(int, ...) is efficient for converting large amounts of data
    P = list(map(int, input_data[2:2+N]))
    W = list(map(int, input_data[2+N:2+N+D]))
    
    # Calculate S_mod = (sum of all P_i) mod MOD
    # sum() is highly optimized in Python
    S_mod = sum(P) % MOD
    
    # Calculate W_sum_mod = (sum of all W_j) mod MOD
    W_sum_mod = sum(W) % MOD
    
    # Calculate P_prod = (product of all P_i) mod MOD
    P_prod = 1
    for p in P:
        P_prod = (P_prod * p) % MOD
        
    # Calculate the modular inverse of S_mod
    # pow(a, MOD - 2, MOD) computes the inverse via Fermat's Little Theorem
    S_inv = pow(S_mod, MOD - 2, MOD)
    
    # ratio = (W_sum / S) mod MOD
    ratio = (W_sum_mod * S_inv) % MOD
    
    # Calculate ratio^N mod MOD
    ratio_pow_N = pow(ratio, N, MOD)
    
    # Final answer R mod MOD = (P_prod * ratio_pow_N) mod MOD
    ans = (P_prod * ratio_pow_N) % MOD
    
    # Output the result to standard output
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

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