Overview

Bonuses are distributed proportionally to each employee’s contribution. We need to find the product of bonuses received by all employees as an irreducible fraction, then output the numerator × modular inverse of the denominator modulo \(998244353\).

Analysis

First, the total bonus \(T_i\) that employee \(i\) receives over \(D\) months can be expressed as:

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

where \(W_{\text{total}} = \sum_{j=1}^{D} W_j\).

Then, the product \(R\) of all employees’ bonuses is:

\[ 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} \]

Looking at this expression, we can see that \(R\) can be handled by treating the numerator and denominator separately.

What about a naive approach?

If we multiply fractions directly, the numbers become extremely large, causing overflow and loss of precision. Even if we reduce fractions using gcd at each step, the computational cost would be too high.

Solution

Since we know the final form, we compute it directly: - Numerator: \(\left(\prod_{i=1}^{N} P_i\right) \cdot W_{\text{total}}^N\) - Denominator: \(S^N\)

We compute everything modulo \(998244353\), and at the end calculate numerator × modular inverse of the denominator.

An additional important point: if \(W_{\text{total}} = 0\), then \(R = 0\), so we can immediately output 0.

Algorithm

1. Read each input and compute \(S = \sum P_i\) and \(W_{\text{total}} = \sum W_j\).
2. If \(W_{\text{total}} = 0\), the answer is 0.
3. Otherwise:
   • \(\text{numerator} = \left(\prod P_i\right) \cdot W_{\text{total}}^N \bmod MOD\)
   • \(\text{denominator} = S^N \bmod MOD\)
4. Finally, output \((\text{numerator}) \cdot (\text{denominator})^{-1} \bmod MOD\).

Here, \((\text{denominator})^{-1} \bmod MOD\) can be computed as \(denominator^{MOD - 2} \bmod MOD\) by Fermat’s little theorem.

Complexity

• Time complexity: \(O(N + D + \log MOD)\)
  • Computing the product of \(P\) takes \(O(N)\)
  • Exponentiation takes \(O(\log MOD)\)
• Space complexity: \(O(N + D)\) (for the input arrays)

Implementation Notes

• Since fast input reading is necessary, sys.stdin.read is used.

• All multiplications and exponentiations involving large numbers are performed while taking \(\bmod 998244353\) at each step.

• In particular, don’t forget to handle the case where \(W_{\text{total}} = 0\).

• For modular inverse, using Python’s built-in function pow(base, exp, mod) is efficient.

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.