Overview

This problem asks us to find the total bonus \(T_i\) that each employee receives over \(D\) months, and then compute the product of these totals across all employees: \(R = \prod_{i=1}^{N} T_i\). At first glance, this appears to require complex calculations, but by organizing the formulas, we can reduce it to a very simple form.

Analysis

1. Simplifying the Formulas

First, let’s organize the total bonus \(T_i\) that employee \(i\) receives over \(D\) months. The amount received in each month \(j\) is \(\frac{P_i \times W_j}{S}\). Summing this from \(j=1\) to \(D\), we get:

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

Here, letting the total bonus fund across all months be \(W_{sum} = \sum_{j=1}^{D} W_j\), we can simplify to: $\(T_i = \frac{P_i \times W_{sum}}{S}\)$

Next, we compute the desired product \(R\) of total bonuses across all employees: $\(R = \prod_{i=1}^{N} T_i = \prod_{i=1}^{N} \left( \frac{P_i \times W_{sum}}{S} \right)\)$

Expanding this product, we can factor out the common coefficient: $\(R = \left( \frac{W_{sum}}{S} \right)^N \times \prod_{i=1}^{N} P_i\)$

2. Using Modular Inverse

The value to compute is \(R = (\prod P_i) \times (W_{sum} \times S^{-1})^N\). Since the constraints guarantee that \(S\) is not a multiple of \(998244353\), we can use Fermat’s little theorem to compute the modular inverse \(S^{-1} \pmod{998244353}\).

Algorithm

1. Computing sums and products of inputs:
   • Compute the sum of all employees’ contributions \(S = \sum P_i \pmod{MOD}\).
   • Compute the sum of all monthly bonus funds \(W_{sum} = \sum W_j \pmod{MOD}\).
   • Compute the product of all employees’ contributions \(P_{prod} = \prod P_i \pmod{MOD}\).
2. Computing the inverse:
   • Compute the modular inverse of \(S\): \(S^{-1} \equiv S^{MOD-2} \pmod{MOD}\).
3. Computing the power:
   • Compute the \(N\)-th power of the ratio: \((\frac{W_{sum}}{S})^N \equiv (W_{sum} \times S^{-1})^N \pmod{MOD}\).
4. Final answer:
   • Output \(P_{prod} \times (W_{sum} \times S^{-1})^N \pmod{MOD}\).

Complexity

• Time complexity: \(O(N + D + \log N)\)
  • \(O(N)\) for computing the sum and product of \(P_i\)
  • \(O(D)\) for computing the sum of \(W_j\)
  • \(O(\log N)\) for exponentiation by squaring.
• Space complexity: \(O(N + D)\)
  • Depends on the arrays used to store input values.

Implementation Notes

• Fast I/O: Since \(N, D\) can be as large as \(10^6\), in Python it is efficient to read all input at once using sys.stdin.read().split() or similar methods.

• Large number computation: Python natively supports arbitrary-precision integers, but by taking MOD at each intermediate step, we can reduce memory consumption and compute efficiently.

• Power function: Python’s pow(a, b, m) internally uses exponentiation by squaring and can compute \(a^b \pmod m\) very efficiently.

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.