概要

各端末からの遷移は「次の端末が1つに決まる」関数グラフなので、
「\(2^b\) 回操作した後の位置」と「そのとき得られる \(2^b\) 桁の値（mod \(M\)）」をダブリングで前計算し、各クエリを \(K\) の2進展開で高速に合成して求める問題です。

考察

この問題では、1回の操作で

• 今いる端末の数字を1桁追加
• 次の端末へ移動

を行います。
クエリごとにこれを \(K\) 回シミュレーションすると、\(K\) は最大 \(10^{18}\) なので到底間に合いません。

---

重要な観察は、「桁列の結合」が次の式で表せることです。

長さ \(a\) の列の値を \(X\)、長さ \(b\) の列の値を \(Y\) とすると、
連結した長さ \(a+b\) の値は

\[ X \cdot 10^b + Y \]

です（最後は mod \(M\) を取ればよい）。

つまり、
「前半ブロック」と「後半ブロック」を合成できるなら、
\(2^0,2^1,2^2,\dots\) のブロックを作っていけます。
これはちょうどダブリング（binary lifting）です。

---

素朴法がだめな理由：

• 各クエリで \(K\) 回回す → 最悪 \(10^{18}\) ステップで不可能
• クエリ数も最大 \(10^5\) あるため、1クエリあたり \(O(\log K)\) 程度まで落とす必要がある

そこで、各端末 \(v\) について

• nxt[b][v]: \(v\) から \(2^b\) 回移動した先
• val[b][v]: \(v\) から \(2^b\) 回操作して得る \(2^b\) 桁の値 mod \(M\)

を持てば、各クエリは \(K\) の立っているbitだけ順に合成して答えられます。

アルゴリズム

1. 初期化（\(b=0\)）

   • nxt[0][v] = P[v]
   • val[0][v] = D[v] mod M
     （1回操作で1桁記録し、1回移動）

2. \(10^{2^b} \bmod M\) の前計算

   • pow10[0] = 10 mod M
   • pow10[b] = pow10[b-1]^2 mod M
     これで pow10[b] = 10^{2^b} mod M になる。

3. ダブリング遷移の構築

   • \(2^b\) ブロックは、\(2^{b-1}\) ブロック2つの連結。
   • mid = nxt[b-1][v]（前半後の位置）
   • nxt[b][v] = nxt[b-1][mid]
   • val[b][v] = val[b-1][v] * 10^{2^{b-1}} + val[b-1][mid] (mod M)

つまり実装式： $\( \text{val}[b][v] = (\text{val}[b-1][v] \cdot \text{pow10}[b-1] + \text{val}[b-1][\text{mid}]) \bmod M \)$

1. 各クエリ処理
   • cur = S_j, ans = 0
   • \(K_j\) の下位bitから見て、bit \(b\) が立っていたら
     • ans = ans * 10^{2^b} + val[b][cur] (mod M)
     • cur = nxt[b][cur]
   • これを \(K_j=0\) になるまで繰り返す。
   • K_j=0 のときは何も合成しないので ans=0 のまま（問題文通り）。

この「ansに後ろへブロックを追加する」順序が大事です。
下位bitから処理しても、毎回「現在の答えを左にシフトしてから新ブロック追加」しているので、桁順は正しく保たれます。

計算量

• 時間計算量: \(O(N \log K_{\max} + Q \log K_{\max})\)
  ここで \(K_{\max} \le 10^{18}\) なので \(\log K_{\max} \approx 60\)。
• 空間計算量: \(O(N \log K_{\max})\)

実装のポイント

• 端末番号は入力が1-indexed、コードでは0-indexedに直す。

• LOG=60 で十分（\(10^{18}<2^{60}\)）。

• pow10[b] は「\(10^{2^b}\) mod \(M\)」を保持する配列。合成時に必須。

• Pythonでも O((N+Q)*60) なので十分高速。
  

• M=1 の場合も全て自動的に 0 になり正しく動く。

  ソースコード

import sys

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

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

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

    # nxt[b][v]: node after 2^b moves from v
    # val[b][v]: value of length 2^b digit string obtained from v, modulo M
    nxt = [[0] * N for _ in range(LOG)]
    val = [[0] * N for _ in range(LOG)]

    for v in range(N):
        nxt[0][v] = P[v]
        val[0][v] = D[v] % M

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

    for b in range(1, LOG):
        nb = nxt[b - 1]
        vb = val[b - 1]
        ncur = nxt[b]
        vcur = val[b]
        mul = pow10[b - 1]
        for v in range(N):
            mid = nb[v]
            ncur[v] = nb[mid]
            vcur[v] = (vb[v] * mul + vb[mid]) % M

    out = []
    for _ in range(Q):
        s, k = input().split()
        s = int(s) - 1
        k = int(k)

        cur = s
        ans = 0
        bit = 0
        while k:
            if k & 1:
                ans = (ans * pow10[bit] + val[bit][cur]) % M
                cur = nxt[bit][cur]
            k >>= 1
            bit += 1
        out.append(str(ans))

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

if __name__ == "__main__":
    main()

---

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