概要

各社員の総ボーナス \(T_i\) の積 \(R=\prod T_i\) を「分数としての値」を保ったまま、法 \(998244353\) 上で \(A\times B^{-1}\) を計算します。結論として \(R\) は簡単な形に整理でき、必要なのは \(\sum P_i\)・\(\prod P_i\)・\(\sum W_j\) の3つだけです。

考察

まず、各社員の総額は [ T_i=\frac{Pi}{S}\times \sum{j=1}^D Wj \quad (S=\sum{i=1}^N Pi) ] なので、積 \(R\) は [ 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} ] と 完全に分解 できます。つまり、各 \(T_i\) を個別に分数で持って掛け合わせる必要はありません。

素朴にやると例えば - 各 \(T_i\) を既約分数で管理して \(N\) 回掛ける
- 分子・分母が巨大化し、\(\gcd\) なども必要になって重い
といった問題が起きます（\(N\le 10^6\) なので間に合いません）。

一方この問題は最終的に「既約分数 \(A/B\) の \(A\times B^{-1}\bmod \text{MOD}\)」が欲しいだけです。法 \(998244353\) は素数で、さらに制約より \(S\) は MOD の倍数ではないので \(S\) の逆元が存在します。よって [ \frac{\prod P_i}{S^N}\equiv \left(\prod P_i\right)\times (S^{-1})^N \pmod{\text{MOD}} ] として、すべてを mod 上で計算できます。

また \(R=0\) になるのはいつか？
\(P_i>0,\ S>0\) より、\(T_i=0\) となるのは \(\sum W_j=0\) のときだけです。したがって - \(\sum W_j=0\) なら答えは \(0\) - それ以外なら上の式で計算
となります。

※ここで注意：\(\sum W_j \bmod \text{MOD}=0\) でも、\(\sum W_j\) が本当に 0 とは限りません。例えば \(\sum W_j=\text{MOD}\) なら \(R\neq 0\) です。よって「\(\sum W_j=0\) の判定」は 整数としての和 で行う必要があります（コードでも sumW を別に持っています）。

アルゴリズム

1. 入力から \(P_i\) を読みながら
   • \(S \bmod \text{MOD}\) を加算で求める
   • \(\prod P_i \bmod \text{MOD}\) を掛け算で求める
2. 入力から \(W_j\) を読みながら
   • \(\sum W_j\)（整数）を求めて、0 判定用に使う
   • \((\sum W_j) \bmod \text{MOD}\) も求める（mod 計算用）
3. もし \(\sum W_j=0\) なら \(R=0\) なので 0 を出力。
4. そうでなければ
   • \(S^{-1}\equiv S^{\text{MOD}-2}\pmod{\text{MOD}}\)（フェルマーの小定理）
   • [ \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}} ] を計算して出力。

（小例）\(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} ] となり、確かに「和」と「積」だけで決まります。

計算量

• 時間計算量: \(O(N+D+\log \text{MOD})\)（累乗計算は \(\log \text{MOD}\)、入力走査が支配的）
• 空間計算量: \(O(1)\)（配列に保持せず逐次処理）

実装のポイント

• 高速入力が必須：\(N,D\le 10^6\) なので、sys.stdin.buffer.read() でまとめて読み、手書きパーサで整数を抜き出しています。

• \(R=0\) 判定は整数の \(\sum W_j\) で行う：sumW_mod==0 ではダメ（\(\sum W_j\) が MOD の倍数の可能性）。

• 逆元は pow(x, MOD-2, MOD)：MOD が素数で、かつ \(S\not\equiv 0\pmod{\text{MOD}}\) が保証されているため安全に使えます。

  ソースコード

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)

この解説は gpt-5.2-high によって生成されました。