概要

各端末は「次に移動する端末」が 1 つだけ決まっているので、移動は一直線にたどれます。
そこで、\(2^b\) 回移動したときの「到達先」と「その間に記録される数字列の値 \(\bmod M\)」をダブリングで前計算し、各問い合わせを高速に処理します。

考察

この問題では、開始端末 \(S\) からちょうど \(K\) 回操作したときにできる数字列

\[ d_1d_2\cdots d_K \]

を整数とみなした値

\[ V=\sum_{t=1}^{K} d_t \cdot 10^{K-t} \]

を \(M\) で割った余りを求めます。

素朴にシミュレーションすると間に合わない

1 回の問い合わせごとに、実際に \(K\) 回移動して数字を記録していく方法を考えると、
\(K\) は最大 \(10^{18}\) なので到底間に合いません。

また、各端末の移動先は 1 つだけなのでグラフは「functional graph（各頂点の出次数が 1）」ですが、
サイクルを見つけて頑張って処理しようとしても、数字列を \(10\) 進数として連結した値を扱う必要があり、実装がかなり複雑になります。

重要な観察：数字列の連結は mod を保ったまま合成できる

たとえば、ある区間で得られる数字列の値が \(A\)、長さが \(L_A\)、
その次の区間で得られる数字列の値が \(B\)、長さが \(L_B\) だとします。

この 2 つをつなげた数字列の値は

\[ A \times 10^{L_B} + B \]

です。
たとえば "31" と "45" をつなげると "3145" で、

\[ 3145 = 31 \times 10^2 + 45 \]

になっています。

つまり、各区間について

• その区間をたどった後の到達先
• その区間でできる数字列の値 \(\bmod M\)

が分かれば、より長い区間の情報を合成できます。

ダブリングが使える

「\(2^b\) 回移動した結果」を前計算しておけば、
\(K\) を 2 進数に分解して答えられます。

ここで、各 \(b\) について

• up[b][i] = 端末 \(i\) から \(2^b\) 回移動した後にいる端末
• val[b][i] = 端末 \(i\) から始めて \(2^b\) 回の操作で記録される数字列の値 \(\bmod M\)

を持てばよいです。

遷移の作り方

\(2^b\) 回の移動は、\(2^{b-1}\) 回移動を 2 回つなげたものです。

まず前半で得られる値を \(A\)、後半を \(B\) とすると、前半・後半の長さはどちらも \(2^{b-1}\) なので、

\[ \text{val}[b][i] = \text{val}[b-1][i] \times 10^{2^{b-1}} + \text{val}[b-1][\text{mid}] \pmod M \]

となります。
ここで \(\text{mid}=\text{up}[b-1][i]\) は、前半を終えた後にいる端末です。

この式を使うために、

\[ 10^{2^b} \bmod M \]

も前計算しておきます。

問い合わせの処理

\(K\) を 2 進数で見て、立っているビットごとに対応する長さ \(2^b\) の区間を順に足していきます。

例えば \(K=13=(1101)_2\) なら、

• \(1\) 回
• \(4\) 回
• \(8\) 回

の区間をこの順に連結すれば、ちょうど先頭から 13 回分になります。

現在までの答えを res、今いる端末を cur とすると、
長さ \(2^b\) の区間を後ろに付け足すときは

\[ \text{res} = \text{res} \times 10^{2^b} + \text{val}[b][cur] \pmod M \]

と更新できます。
そして cur は up[b][cur] に移ります。

これで 1 問い合わせを \(O(\log K)\) で処理できます。

アルゴリズム

1. 各端末の数字 \(D_i\)、移動先 \(P_i\) を読む。
2. \(M=1\) なら、どんな値も \(\bmod 1\) では \(0\) なので全問い合わせの答えは \(0\)。
3. \(K \le 10^{18} < 2^{60}\) なので、\(b=0,\dots,59\) まで前計算する。
4. pow10[b] = 10^{2^b} \bmod M を前計算する。
   • pow10[0] = 10 mod M
   • pow10[b] = pow10[b-1]^2 mod M
5. ダブリング配列を作る。
   • 基底：
     • up[0][i] = P_i
     • val[0][i] = D_i
   • 遷移：
     • mid = up[b-1][i]
     • up[b][i] = up[b-1][mid]
     • val[b][i] = (val[b-1][i] * pow10[b-1] + val[b-1][mid]) mod M
6. 各問い合わせ \((S, K)\) に対して：
   • cur = S, res = 0
   • \(K\) の下位ビットから順に見て、\(b\) ビット目が立っていたら
     • res = (res * pow10[b] + val[b][cur]) mod M
     • cur = up[b][cur]
   • 最後の res を出力する。
7. \(K=0\) の場合は一度も更新されず、res=0 のままなのでそのまま正しい。

計算量

• 時間計算量: \(O((N+Q)\log K_{\max}) = O((N+Q)\cdot 60)\)
• 空間計算量: \(O(N\log K_{\max}) = O(N\cdot 60)\)

実装のポイント

• 連結の式の向きに注意してください。
  先に現れる数字列を後ろの桁数だけ左にずらすので、

$\( A \text{ の後に } B \text{ を連結} \Rightarrow A \times 10^{|B|} + B \)$

です。 - 前計算でも問い合わせ処理でも、この「前の値を \(10^{\text{長さ}}\) 倍してから足す」という形になります。 - Python の通常の list[int] で大きな 2 次元配列を持つとメモリが厳しいため、このコードでは array('I') を使ってメモリを節約しています。 - B = 60 で十分です。理由は

$\( 10^{18} < 2^{60} \)$

だからです。

ソースコード

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline
    N, Q, M = map(int, input().split())

    if M == 1:
        for _ in range(N):
            input()
        out = ["0"] * Q
        for _ in range(Q):
            input()
        sys.stdout.write("\n".join(out))
        return

    D = array('I', [0]) * (N + 1)
    P = array('I', [0]) * (N + 1)

    for i in range(1, N + 1):
        d, p = map(int, input().split())
        D[i] = d
        P[i] = p

    B = 60  # since K <= 1e18 < 2^60

    pow10 = [0] * B
    pow10[0] = 10 % M
    for b in range(1, B):
        pow10[b] = (pow10[b - 1] * pow10[b - 1]) % M

    up = [P]
    val = [D]

    idx_range = range(1, N + 1)
    for b in range(1, B):
        prev_up = up[-1]
        prev_val = val[-1]
        cur_up = array('I', [0]) * (N + 1)
        cur_val = array('I', [0]) * (N + 1)
        mul = pow10[b - 1]

        for i in idx_range:
            mid = prev_up[i]
            cur_up[i] = prev_up[mid]
            cur_val[i] = (prev_val[i] * mul + prev_val[mid]) % M

        up.append(cur_up)
        val.append(cur_val)

    out = []
    up_local = up
    val_local = val
    pow10_local = pow10

    for _ in range(Q):
        s, k = map(int, input().split())
        cur = s
        res = 0
        b = 0
        while k:
            if k & 1:
                res = (res * pow10_local[b] + val_local[b][cur]) % M
                cur = up_local[b][cur]
            k >>= 1
            b += 1
        out.append(str(res))

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

if __name__ == "__main__":
    main()

---

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