Overview

This problem requires efficiently computing, for each of \(Q\) simulations (queries), the remainder when dividing the product of \(N\) given integers by \(M\), after replacing exactly one element.

Analysis

Naive Approach and Its Limitations

For each query, if we replace the specified element and then compute the product of all elements, it takes \(O(N)\) time per query. Since there are \(Q\) queries, the overall time complexity is \(O(NQ)\). Given the constraints \(N, Q \leq 2 \times 10^5\), the worst case requires approximately \(4 \times 10^{10}\) computations, which will not fit within the time limit (resulting in TLE).

Optimization Idea (Using Inverses)

We precompute the product of all elements \(S = P_1 \times P_2 \times \cdots \times P_N \pmod M\). When changing the production efficiency of factory \(X_j\) from \(P_{X_j}\) to \(V_j\), the product after the change can be expressed as:

\[ (\text{product after change}) = S \times (P_{X_j})^{-1} \times V_j \pmod M \]

Here, \((P_{X_j})^{-1}\) is the modular inverse of \(P_{X_j}\) modulo \(M\). Using this, we can answer each query in \(O(1)\) or \(O(\log M)\) time.

Exception Handling Due to the Existence of “0”

However, this approach has a pitfall: when there exist elements where \(P_i \equiv 0 \pmod M\) (hereafter referred to as “elements that are \(0\)”). Since the inverse of \(0\) does not exist, we cannot directly apply the above formula. Therefore, we perform case analysis based on the count \(Z\) of elements in the initial sequence \(P\) whose remainder when divided by \(M\) is \(0\).

Case 1: \(Z \geq 2\) (Two or more zeros)

If there are two or more elements that are \(0\) in the initial state, no matter which single element \(X_j\) we replace with \(V_j\), at least one element that is \(0\) will always remain among the other \(N-1\) elements. Therefore, regardless of the replacement, the overall product is always \(0\).

Case 2: \(Z = 1\) (Exactly one zero)

There is exactly one element that is \(0\) in the initial state; let its index be \(zero\_idx\). - When the element being replaced \(X_j\) is \(zero\_idx\): Since the only element that was \(0\) is being replaced with \(V_j\), the overall product may become non-zero. The answer in this case is “the product of all elements except \(zero\_idx\)” multiplied by \(V_j\). - When the element being replaced \(X_j\) is not \(zero\_idx\): Since the element at \(zero\_idx\) (with value \(0\)) remains unchanged, the overall product is always \(0\).

Case 3: \(Z = 0\) (No zeros)

Since none of the \(P_i\) are divisible by \(M\), inverses exist for all elements. We precompute the total product \(S\), and for each query, we compute \(S \times (P_{X_j})^{-1} \times V_j \pmod M\). By Fermat’s little theorem, if \(M\) is prime, the inverse of \(P_i\) can be obtained as \(P_i^{M-2} \pmod M\).

---

Algorithm

1. Input and Preprocessing:
   • Convert each \(P_i\) to its remainder when divided by \(M\) in advance.
   • Store the indices of elements where \(P_i = 0\) in a list zeros.
2. Case-based Processing:
   • When \(Z \geq 2\):
     • Output 0 for all queries.
   • When \(Z = 1\):
     • Let \(zero\_idx\) be the index of the only element that is \(0\).
     • Precompute the product \(S'\) of all elements except the one at \(zero\_idx\).
     • For each query \((X_j, V_j)\), output \(S' \times V_j \pmod M\) if \(X_j = zero\_idx\), otherwise output 0.
   • When \(Z = 0\):
     • Compute the total product \(S\).
     • Compute the inverse \((P_i)^{-1} \pmod M\) for each element \(P_i\). To avoid redundant inverse computations for the same value, use memoization (storing results in an associative array).
     • For each query \((X_j, V_j)\), output \(S \times (P_{X_j})^{-1} \times V_j \pmod M\).

---

Complexity

• Time Complexity: \(O(N \log M + Q)\)

  • The worst case occurs when \(Z = 0\).
  • Computing the total product takes \(O(N)\) time.
  • Computing the inverse of each element takes \(O(\log M)\) per element using fast exponentiation. Computing inverses for all elements takes \(O(N \log M)\) in the worst case.
  • Query processing takes \(O(1)\) per query, so the total is \(O(Q)\).
  • Therefore, the overall time complexity is \(O(N \log M + Q)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N + Q)\)

  • \(O(N + Q)\) memory is used for storing the array \(P\), the inverses, and the input/output buffers for queries.

---

Implementation Notes

• Fast I/O: In Python, a large number of I/O operations can become a bottleneck. By reading all input at once using sys.stdin.read().split() and writing all output at once using sys.stdout.write, execution time can be significantly reduced.

• Memoization of Inverses: If the same value \(P_i\) appears multiple times in the array, calling pow(val, M - 2, M) each time results in redundant computation. By recording (memoizing) previously computed inverses using a dictionary (hash map), we can achieve constant-factor speedup.

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    M = int(input_data[2])
    
    P = [int(x) % M for x in input_data[3:3+N]]
    
    queries_raw = input_data[3+N:3+N+2*Q]
    
    zeros = []
    for i in range(N):
        if P[i] == 0:
            zeros.append(i)
            
    Z = len(zeros)
    out = []
    
    if Z >= 2:
        # 常に0になる
        out = ['0'] * Q
    elif Z == 1:
        zero_idx = zeros[0]
        # 唯一の0以外の要素の積を計算
        S_prime = 1
        for i in range(N):
            if i != zero_idx:
                S_prime = (S_prime * P[i]) % M
        
        for q in range(Q):
            X_j = int(queries_raw[2*q]) - 1
            V_j = int(queries_raw[2*q+1]) % M
            if X_j == zero_idx:
                ans = (S_prime * V_j) % M
                out.append(str(ans))
            else:
                out.append('0')
    else:
        # Z == 0 の場合
        S = 1
        for x in P:
            S = (S * x) % M
            
        # 逆元をメモ化しながら計算
        memo = {}
        invP = [0] * N
        for i in range(N):
            val = P[i]
            if val not in memo:
                memo[val] = pow(val, M - 2, M)
            invP[i] = memo[val]
            
        for q in range(Q):
            X_j = int(queries_raw[2*q]) - 1
            V_j = int(queries_raw[2*q+1]) % M
            ans = (S * invP[X_j] % M * V_j) % M
            out.append(str(ans))
            
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

---

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