Overview

We compute \(R=\prod T_i\), the product of each employee’s total bonus \(T_i\), as \(A\times B^{-1}\) modulo \(998244353\) while preserving the value as a fraction. In conclusion, \(R\) simplifies to a clean form, and all we need are three quantities: \(\sum P_i\), \(\prod P_i\), and \(\sum W_j\).

Analysis

First, each employee’s total amount is [ T_i=\frac{Pi}{S}\times \sum{j=1}^D Wj \quad (S=\sum{i=1}^N Pi) ] so the product \(R\) is [ R=\prod{i=1}^N\left(\frac{Pi}{S}\times \sum{j=1}^D Wj\right) = \left(\sum{j=1}^D Wj\right)^N \times \frac{\prod{i=1}^N P_i}{S^N} ] which completely factors. In other words, there is no need to maintain each \(T_i\) individually as a fraction and multiply them together.

A naive approach would, for example: - Manage each \(T_i\) as a reduced fraction and multiply \(N\) times - The numerator and denominator grow enormous, requiring \(\gcd\) computations and becoming too slow

Such approaches are problematic (since \(N\le 10^6\), they won’t finish in time).

However, in this problem, all we ultimately need is “\(A\times B^{-1}\bmod \text{MOD}\)” for the reduced fraction \(A/B\). The modulus \(998244353\) is prime, and from the constraints \(S\) is not a multiple of MOD, so the modular inverse of \(S\) exists. Therefore [ \frac{\prod P_i}{S^N}\equiv \left(\prod P_i\right)\times (S^{-1})^N \pmod{\text{MOD}} ] and everything can be computed under mod.

When does \(R=0\)? Since \(P_i>0\) and \(S>0\), we have \(T_i=0\) only when \(\sum W_j=0\). Therefore: - If \(\sum W_j=0\), the answer is \(0\) - Otherwise, compute using the formula above

※Important note: Even if \(\sum W_j \bmod \text{MOD}=0\), the actual value of \(\sum W_j\) might not be 0. For example, if \(\sum W_j=\text{MOD}\), then \(R\neq 0\). Therefore, the check “\(\sum W_j=0\)” must be done using the integer sum (in the code, sumW is maintained separately for this purpose).

Algorithm

1. While reading \(P_i\) from input:
   • Compute \(S \bmod \text{MOD}\) by accumulating additions
   • Compute \(\prod P_i \bmod \text{MOD}\) by accumulating multiplications
2. While reading \(W_j\) from input:
   • Compute \(\sum W_j\) (as an integer) for the zero check
   • Also compute \((\sum W_j) \bmod \text{MOD}\) (for mod calculations)
3. If \(\sum W_j=0\), then \(R=0\), so output 0.
4. Otherwise:
   • \(S^{-1}\equiv S^{\text{MOD}-2}\pmod{\text{MOD}}\) (Fermat’s little theorem)
   • [ \text{ans}= \left(\sum W_j \bmod \text{MOD}\right)^N \times \left(\prod P_i \bmod \text{MOD}\right) \times \left(S^{-1}\right)^N \pmod{\text{MOD}} ] Compute and output this.

(Small example) When \(N=2\): [ R=T_1T_2= \left(\frac{P_1}{S}\sum W\right)\left(\frac{P_2}{S}\sum W\right) =(\sum W)^2\cdot \frac{P_1P_2}{S^2} ] which indeed depends only on the “sum” and the “product”.

Complexity

• Time complexity: \(O(N+D+\log \text{MOD})\) (exponentiation takes \(\log \text{MOD}\); input scanning dominates)
• Space complexity: \(O(1)\) (processed incrementally without storing in arrays)

Implementation Notes

• Fast input is essential: Since \(N,D\le 10^6\), we read all input at once with sys.stdin.buffer.read() and extract integers using a hand-written parser.

• The \(R=0\) check must use the integer value of \(\sum W_j\): Checking sumW_mod==0 is insufficient (since \(\sum W_j\) could be a multiple of MOD).

• Modular inverse uses pow(x, MOD-2, MOD): This is safe because MOD is prime and \(S\not\equiv 0\pmod{\text{MOD}}\) is guaranteed.

  Source Code

import sys

MOD = 998244353

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
D = next_int()

prodP = 1
sumP_mod = 0

for _ in range(N):
    p = next_int()
    prodP = (prodP * (p % MOD)) % MOD
    sumP_mod += p
    sumP_mod %= MOD

sumW = 0
sumW_mod = 0
for _ in range(D):
    w = next_int()
    sumW += w
    sumW_mod += w
    sumW_mod %= MOD

if sumW == 0:
    print(0)
else:
    invS = pow(sumP_mod, MOD - 2, MOD)
    ans = pow(sumW_mod, N, MOD)
    ans = (ans * prodP) % MOD
    ans = (ans * pow(invS, N, MOD)) % MOD
    print(ans)

This editorial was generated by gpt-5.2-high.