概要

この問題は、\(N\) 個の工場の生産効率の総積を素数 \(M\) で割った余りを管理し、クエリごとに1つの工場の生産効率を一時的に変更したときの総積（\(\pmod M\)）を高速に求める問題です。

考察

素朴なアプローチとその限界

最も単純な方法は、クエリごとにすべての工場の生産効率の積を掛け合わせ、それを \(M\) で割った余りを計算することです。 しかし、この方法では1つのクエリにつき \(O(N)\) の計算量が必要になります。クエリが \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となります。 制約は \(N, Q \leq 2 \times 10^5\) であるため、最悪の場合に約 \(4 \times 10^{10}\) 回の計算が必要となり、実行時間制限（通常2秒）に間に合わず TLE（実行時間制限超過） となってしまいます。

逆元を用いた高速化

クエリごとに一から掛け算をやり直すのではなく、「事前に求めた全要素の総積」から「変更前の値を取り除き」、「変更後の値を掛け合わせる」というアプローチを考えます。

\(M\) を法とする世界（\(\pmod M\)）において、ある値 \(A\) で「割る」という操作は、\(A\) の乗法逆元 \(A^{-1}\) を掛ける ことと同値です。 問題文より \(M\) は素数であるため、フェルマーの小定理（\(A^{M-1} \equiv 1 \pmod M\)）より、逆元は以下のように求められます。

\[A^{-1} \equiv A^{M-2} \pmod M\]

これを利用すると、元の総積を \(All\)、変更前の値を \(P_{X}\)、変更後の値を \(V\) としたとき、新しい総積は次のように \(O(\log M)\) で計算できます。

\[\text{新しい総積} = All \times P_{X}^{-1} \times V \pmod M\]

ゼロ（\(M\) の倍数）の壁

しかし、この方法には1つ大きな落とし穴があります。 それは、\(0 \pmod M\) となる要素（\(M\) の倍数）が存在する場合です。 \(\pmod M\) において \(0\) の逆元 \(0^{-1}\) は存在しないため、上記の方法をそのまま適用するとゼロ除算（逆元が存在しないことによるエラー）が発生します。 また、1つでも \(0\) が含まれていると全体の積は \(0\) になりますが、その \(0\) になっている要素を \(0\) 以外の値に変更した場合は、全体の積が \(0\) 以外の値になり得ます。

この問題を解決するために、以下の2つの情報を分けて管理します。 1. \(Z\) : \(P_i \equiv 0 \pmod M\) となる要素の個数 2. \(S\) : \(P_i \not\equiv 0 \pmod M\) である要素「のみ」を掛け合わせた積（\(\pmod M\)）

このように管理することで、以下のように状態を更新できます。 - 要素を取り除くとき： - 取り除く値が \(0\) なら、ゼロの個数 \(Z\) を \(1\) 減らす。 - \(0\) 以外なら、\(S\) にその値の逆元を掛ける。 - 新しい要素を追加するとき： - 追加する値が \(0\) なら、ゼロの個数 \(Z\) を \(1\) 増やす。 - \(0\) 以外なら、\(S\) にその値を掛ける。

最終的な答えは、一時的なゼロの個数 \(Z\) が \(1\) 個以上なら \(0\)、そうでなければ一時的な積 \(S\) となります。

アルゴリズム

1. 初期状態の計算と逆元の事前計算:

   • 初期配列 \(P\) を読み込みながら、各要素が \(0 \pmod M\) であるかを判定します。
   • \(0\) であれば \(Z\) をインクリメントし、\(0\) でなければ全体の積 \(S\) に掛け合わせます。
   • 同時に、各要素 \(P_i \not\equiv 0 \pmod M\) に対して、フェルマーの小定理を用いて逆元 \(P_i^{-1} \pmod M\) を事前計算して配列 P_inv に保存しておきます。

2. クエリの処理: 各クエリ \((X, V)\) に対し、元の状態 \(Z, S\) を汚さないように一時変数 temp_Z = Z, temp_S = S を作成して以下を行います。

   • 元の値 \(P_X\) の影響を取り除く:
     • \(P_X \equiv 0 \pmod M\) なら temp_Z を \(1\) 減らす。
     • そうでなければ、temp_S に事前計算した逆元 P_inv[X] を掛ける。
   • 新しい値 \(V\) の影響を追加する:
     • \(V \equiv 0 \pmod M\) なら temp_Z を \(1\) 増やす。
     • そうでなければ、temp_S に \(V\) を掛ける。
   • 結果の出力:
     • temp_Z > 0 なら \(0\) を出力する。
     • そうでなければ temp_S を出力する。

計算量

• 時間計算量: \(O(N \log M + Q)\)

  • 事前計算において、各要素の逆元を求めるために繰り返し二乗法を用います。これに \(O(N \log M)\) かかります。
  • 各クエリは、あらかじめ計算された逆元を利用するため、乗算と加減算のみの \(O(1)\) で処理できます。\(Q\) 個のクエリ全体で \(O(Q)\) です。
  • 全体で \(O(N \log M + Q)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • 工場の初期生産効率を保持する配列 P と、逆元を保持する配列 P_inv のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速入出力: \(N, Q\) の値が最大 \(2 \times 10^5\) と非常に大きいため、C++では cin.tie(NULL); ios_base::sync_with_stdio(false); を用いて入出力を高速化しています。これを行わない場合、入出力ボトルネックで TLE になる可能性があります。

• 一時変数の利用: 各クエリは独立しているため、元の \(Z\) や \(S\) を直接書き換えてしまうと、次のクエリに影響が出てしまいます。クエリごとに temp_Z と temp_S にコピーして処理することで、元の状態を復元する複雑な処理を回避しています。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

// 繰り返し二乗法による冪乗計算
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// モジュラ逆数の計算
long long modInverse(long long n, long long m) {
    return power(n, m - 2, m);
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    long long M;
    if (!(cin >> N >> Q >> M)) return 0;

    vector<long long> P(N + 1);
    long long S = 1;
    int Z = 0;

    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
        long long val = P[i] % M;
        if (val == 0) {
            Z++;
        } else {
            S = (S * val) % M;
        }
    }

    // 各要素の逆元を事前計算しておく
    vector<long long> P_inv(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        long long val = P[i] % M;
        if (val != 0) {
            P_inv[i] = modInverse(val, M);
        }
    }

    for (int j = 0; j < Q; ++j) {
        int X;
        long long V;
        cin >> X >> V;

        long long orig_val = P[X] % M;
        long long new_val = V % M;

        int temp_Z = Z;
        long long temp_S = S;

        // 元の値の影響を取り除く
        if (orig_val == 0) {
            temp_Z--;
        } else {
            temp_S = (temp_S * P_inv[X]) % M;
        }

        // 新しい値の影響を追加する
        if (new_val == 0) {
            temp_Z++;
        } else {
            temp_S = (temp_S * new_val) % M;
        }

        // 結果の出力
        if (temp_Z > 0) {
            cout << 0 << "\n";
        } else {
            cout << temp_S << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。