概要

\(N\) 個の工場の生産効率の積を素数 \(M\) で割った余りを求める問題で、各クエリでは1つの工場の値だけを変更した場合の答えを独立に計算する。

考察

素朴なアプローチの問題点

各クエリごとに \(N\) 個の値の積を計算すると、\(O(NQ)\) となり最大 \(4 \times 10^{10}\) 回の演算が必要で TLE になります。

重要な気づき

クエリで工場 \(X\) の値を \(V\) に変えたときの答えは：

\[\frac{\text{全体の積}}{P_X} \times V \pmod{M}\]

と書けます。\(M\) が素数なので、\(P_X\) が \(M\) の倍数でなければフェルマーの小定理で逆元を計算できます。

\(P_i\) が \(M\) の倍数の場合の問題

\(P_X \equiv 0 \pmod{M}\) のとき、\(P_X\) の逆元は存在しません。そこで場合分けが必要です。

核となるアイデア: \(P_i \bmod M = 0\) となる工場の個数（zero_count）と、それ以外の工場の積（product_nonzero）を事前に計算しておきます。

場合分け

変更対象の工場 \(X\) について、元の値 old = P[X] mod M と新しい値 v_mod = V mod M で場合分けします：

1. old = 0 かつ v_mod = 0: ゼロの個数は変わらず、積は \(0\)
2. old = 0 かつ v_mod ≠ 0: 他にまだゼロがあれば積は \(0\)、なければ product_nonzero × v_mod mod M
3. old ≠ 0 かつ v_mod = 0: 積に \(0\) が含まれるので答えは \(0\)
4. old ≠ 0 かつ v_mod ≠ 0: 他にゼロがあれば答えは \(0\)、なければ product_nonzero × old⁻¹ × v_mod mod M

アルゴリズム

1. 各 \(P_i\) を \(M\) で割った余り P_mod[i] を計算する
2. zero_count（\(P_i \bmod M = 0\) の個数）と product_nonzero（\(P_i \bmod M \neq 0\) であるものの積 mod \(M\)）を前計算する
3. 各クエリで上記の場合分けに従って \(O(1)\) で（逆元計算は \(O(\log M)\) で）答えを求める

具体例: \(N=3\), \(M=5\), \(P = [2, 5, 3]\) の場合 - P_mod = [2, 0, 3]、zero_count = 1、product_nonzero = 6 mod 5 = 1 - クエリ「工場2を7に変更」→ old=0, v_mod=2, 他にゼロなし → 答え = \(1 \times 2 = 2\) - クエリ「工場1を4に変更」→ old=2, v_mod=4, zero_count>0 → 答え = \(0\)

計算量

• 時間計算量: \(O(N + Q \log M)\)（前処理 \(O(N)\)、各クエリで逆元計算に \(O(\log M)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• フェルマーの小定理により、\(M\) が素数のとき \(a^{-1} \equiv a^{M-2} \pmod{M}\)（ただし \(a \not\equiv 0\)）。Pythonでは pow(a, M-2, M) で高速に計算可能。

• \(V_j = 0\) のケースがあるため、v_mod = 0 の処理を忘れないこと。

• 各シミュレーションは独立なので、元の配列を変更しないように注意する。

• 入出力が多いため、sys.stdin.readline や一括出力を使って高速化する。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    # Compute total product mod M
    total_product = 1
    for p in P:
        total_product = total_product * p % M
    
    # For each query, we need total_product / P[X-1] * V mod M
    # Since M is prime, we can use Fermat's little theorem for modular inverse
    # But if P[X-1] % M == 0, we can't compute inverse directly.
    
    # Strategy: count how many P_i are divisible by M, and handle cases.
    # Let zero_count = number of P_i where P_i % M == 0
    # Let product_nonzero = product of (P_i % M) for all i where P_i % M != 0, mod M
    
    P_mod = [p % M for p in P]
    
    zero_count = 0
    product_nonzero = 1
    for pm in P_mod:
        if pm == 0:
            zero_count += 1
        else:
            product_nonzero = product_nonzero * pm % M
    
    out = []
    for _ in range(Q):
        x, v = map(int, input().split())
        x -= 1  # 0-indexed
        v_mod = v % M
        old = P_mod[x]
        
        if old == 0:
            # This element was contributing to zero_count
            new_zero_count = zero_count - 1
            # product without this element = product_nonzero * (product of other zeros=0 if new_zero_count>0)
            if v_mod == 0:
                # Replace 0 with 0: still zero_count zeros among others + this one = same
                # All products: zero_count zeros total, result is 0
                out.append(0)
            else:
                # new_zero_count zeros remain among other elements
                if new_zero_count > 0:
                    # There are still other zeros, so product = 0 regardless of v
                    out.append(0)
                else:
                    # No more zeros among others, product = product_nonzero * v_mod % M
                    out.append(product_nonzero * v_mod % M)
        else:
            # old != 0
            if v_mod == 0:
                # Adding a zero
                new_zero_count = zero_count  # zeros among other elements (unchanged)
                # product = (product of others) * 0 = 0 if v_mod=0
                # But wait, product of others might already be 0 if zero_count > 0
                # Regardless, multiplying by 0 gives 0
                out.append(0)
            else:
                # Neither old nor new is zero mod M
                if zero_count > 0:
                    # There are zeros among other elements (since old != 0, removing old doesn't change zero_count)
                    # product of all others includes zeros -> 0, times v_mod -> 0
                    out.append(0)
                else:
                    # No zeros anywhere, straightforward
                    # product_without_x = product_nonzero * modinv(old) % M
                    # answer = product_without_x * v_mod % M
                    inv_old = pow(old, M - 2, M)
                    ans = product_nonzero * inv_old % M * v_mod % M
                    out.append(ans)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。