Overview

Using the product of the original array \(P_1,\dots,P_N\) modulo \(M\) (a prime) as a base, we efficiently compute the product \(\bmod M\) when exactly one element is replaced by \(V\) for each query.

Analysis

If we naively compute for each query: - Calculate the product \(P_1\times\cdots\times P_N\) from scratch each time

this costs \(O(N)\) per query, resulting in \(O(NQ)\) overall, which is far too slow for \(N,Q\le 2\times 10^5\).

The key observation is as follows:

• The product after replacement can be written as
  $\((P_1\cdots P_N)\times P_{X}^{-1}\times V \pmod M\)\( (when \)P_X \not\equiv 0 \pmod M$).
• Since \(M\) is prime, for any \(a\not\equiv 0\pmod M\), the modular inverse \(a^{-1}\) always exists and can be computed by Fermat’s little theorem:
  $\(a^{-1}\equiv a^{M-2}\pmod M\)$
• However, if any \(P_i \equiv 0 \pmod M\) is present, the inverse does not exist, and the product tends to become 0.
  Therefore, we can handle this cleanly by counting “the number of \(P_i \bmod M\) that are 0” and doing case analysis.

Specifically, letting \(P_i' = P_i \bmod M\): - If there are 2 or more zeros, then even after replacing one of them, at least one zero remains, so the product is always 0. - If there is exactly 1 zero, the product can become non-zero only when we replace the element at that zero position. - If there are 0 zeros, we can update in one step using the modular inverse.

With this approach, each query can be processed in \(O(1)\) (with inverse computation done in preprocessing).

Algorithm

1. Read input and compute \(P_i' = P_i \bmod M\).
2. Precompute the following:
   • zero_cnt: the number of elements where \(P_i'=0\)
   • prod_nonzero: the product of all elements where \(P_i'\ne 0\) (modulo \(M\))
3. Case analysis:
   • zero_cnt >= 2
     The answer is always 0 for any query.
   • zero_cnt == 1
     When a query replaces position \(x\) with \(v\), let \(v' = v \bmod M\):
     • If the original \(P_x'==0\) (replacing the zero position), the answer is
       $\(\text{prod\_nonzero} \times v' \bmod M\)\( (of course, if \)v’=0$ then the answer is 0)
     • If replacing any other position, the zero remains, so the answer is 0.
   • zero_cnt == 0
     Prepare the total product total = prod_nonzero, and for each \(i\), precompute the inverse
     $\(\text{inv}[i] = (P_i')^{M-2}\bmod M\)\( For a query \)(x,v)$:
     • If \(v'=0\), the answer is 0
     • Otherwise:
       $\(\text{ans} = \text{total} \times \text{inv}[x] \times v' \bmod M\)$

Simple Example

\(M=7\), \(P'=[2,0,3]\) (1 zero), prod_nonzero = 2\times 3=6. - Replacing \(x=2\) (the zero position) with \(v=5\): the answer is \(6\times 5=30\equiv 2\pmod 7\). - Replacing \(x=1\) with anything: since the zero at position 2 remains, the answer is 0.

Complexity

• Time complexity:
  Preprocessing computes \(N\) modular inverses in \(O(N\log M)\), and each query is \(O(1)\) for a total of \(O(Q)\).
  Overall: \(O(N\log M + Q)\)
• Space complexity:
  Storing arrays (\(P'\) and inverses): \(O(N)\)

Implementation Notes

• Always take \(P_i\) and \(V_j\) modulo \(M\) first before processing (zero checks are also done after taking \(\bmod M\)).

• Modular inverses are computed using pow(a, M-2, M), leveraging the fact that \(M\) is prime.

• When \(P_i'\equiv 0\), the inverse does not exist, so the case analysis using zero_cnt is essential.

• Since \(N,Q\) can be large, using fast I/O (such as sys.stdin.buffer.read()) helps ensure stable performance.

  Source Code

import sys

def read_ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield x

it = read_ints()
N = next(it)
Q = next(it)
M = next(it)

P = [next(it) for _ in range(N)]
Pmod = [p % M for p in P]

zero_cnt = 0
prod_nonzero = 1
for a in Pmod:
    if a == 0:
        zero_cnt += 1
    else:
        prod_nonzero = (prod_nonzero * a) % M

inv = None
total = None
if zero_cnt == 0:
    total = prod_nonzero
    inv = [0] * N
    exp = M - 2
    for i, a in enumerate(Pmod):
        inv[i] = pow(a, exp, M)

out = []
for _ in range(Q):
    x = next(it) - 1
    v = next(it)
    vx = v % M

    if zero_cnt >= 2:
        out.append("0")
        continue

    if zero_cnt == 1:
        if Pmod[x] == 0:
            if vx == 0:
                out.append("0")
            else:
                out.append(str((prod_nonzero * vx) % M))
        else:
            out.append("0")
        continue

    # zero_cnt == 0
    if vx == 0:
        out.append("0")
    else:
        ans = total * inv[x] % M
        ans = ans * vx % M
        out.append(str(ans))

sys.stdout.write("\n".join(out))

This editorial was generated by gpt-5.2-high.