概要

関数グラフ（各ノードの出次数が1のグラフ）上を歩きながら数字を記録し、それを10進数として解釈した値を \(M\) で割った余りを求める問題です。操作回数 \(K\) が最大 \(10^{18}\) と非常に大きいため、ダブリング（繰り返し二乗法的な前処理） を用いて高速に処理します。

考察

値の計算式を整理する

端末 \(S\) から出発して \(K\) 回の操作で訪問する端末を順に \(u_0, u_1, \ldots, u_{K-1}\)（\(u_0 = S\), \(u_{t+1} = P_{u_t}\)）とすると、得られる値は：

\[V = D[u_0] \cdot 10^{K-1} + D[u_1] \cdot 10^{K-2} + \cdots + D[u_{K-1}] \cdot 10^0\]

これは「1桁ずつ数字を右に追加していく」操作と同じです。つまり、\(V\) を逐次的に計算するなら：

\[V \leftarrow V \times 10 + D[\text{現在の端末}]\]

を \(K\) 回繰り返せばよいですが、\(K\) が最大 \(10^{18}\) なのでそのままではTLEになります。

素朴なアプローチの問題点

1ステップずつシミュレーションすると \(O(K)\) かかり、\(K \leq 10^{18}\) では到底間に合いません。

解決のカギ：区間の連結

長さ \(L_1\) の区間（値 \(V_1\)）と長さ \(L_2\) の区間（値 \(V_2\)）を連結すると：

\[V_{\text{combined}} = V_1 \times 10^{L_2} + V_2\]

この性質を使えば、ダブリングで \(2^k\) ステップ分の情報をまとめて管理できます。

アルゴリズム

ダブリングテーブルの構築

各ノード \(u\) と各 \(k = 0, 1, \ldots, 60\) に対して以下を前計算します：

• \(\text{jump}[k][u]\)：ノード \(u\) から \(2^k\) ステップ進んだ先のノード
• \(\text{val}[k][u]\)：ノード \(u\) から \(2^k\) ステップ分の数字列を10進数として解釈した値（\(\bmod M\)）
• \(\text{pow10}[k] = 10^{2^k} \bmod M\)

初期化（\(k = 0\)、1ステップ分）： - \(\text{jump}[0][u] = P[u]\) - \(\text{val}[0][u] = D[u] \bmod M\) - \(\text{pow10}[0] = 10 \bmod M\)

遷移（\(k \geq 1\)）：

\(2^k\) ステップは、前半 \(2^{k-1}\) ステップ＋後半 \(2^{k-1}\) ステップと分解できます。

• \(\text{mid} = \text{jump}[k-1][u]\)（前半を進んだ先のノード）
• \(\text{jump}[k][u] = \text{jump}[k-1][\text{mid}]\)
• \(\text{val}[k][u] = \text{val}[k-1][u] \times \text{pow10}[k-1] + \text{val}[k-1][\text{mid}] \pmod{M}\)
• \(\text{pow10}[k] = \text{pow10}[k-1]^2 \bmod M\)

クエリの処理

\(K\) を2進展開し、ビットが立っている位置 \(k\) に対応する \(2^k\) ステップ分の区間を上位ビットから順に連結していきます。

具体例として \(K = 5 = (101)_2\) の場合： 1. まず \(2^2 = 4\) ステップ分を処理 2. 次に \(2^0 = 1\) ステップ分を追加連結

連結の際は：

\[\text{cur\_val} = \text{cur\_val} \times 10^{2^k} + \text{val}[k][\text{cur\_node}] \pmod{M}\]

としてから、\(\text{cur\_node}\) を \(\text{jump}[k][\text{cur\_node}]\) に更新します。

計算量

• 時間計算量: \(O(N \log K_{\max} + Q \log K_{\max})\)（前処理に \(O(N \log K_{\max})\)、各クエリに \(O(\log K_{\max})\)）
• 空間計算量: \(O(N \log K_{\max})\)（ダブリングテーブルの保持）

ここで \(\log K_{\max} \approx 61\) です。

実装のポイント

• \(K = 0\) の特殊処理：操作を1回も行わない場合は \(V = 0\) なので、\(0 \bmod M\) を出力します。

• ビットを上位から処理：区間の連結は「前に追加」ではなく「後ろに追加」なので、\(K\) の上位ビットから順に処理することで、先に来る区間から順に蓄積できます。

• \(M = 1\) の場合：すべての答えが \(0\) になりますが、コード中の % M で自然に処理されます。

• メモリ効率：\(N + Q \leq 1.5 \times 10^5\) という制約があるため、\(N\) が大きいときは \(Q\) が小さく、ダブリングテーブルの全体サイズが適切に収まります。

  ソースコード

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    D = [0] * (N + 1)
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        D[i] = int(input_data[idx]); idx += 1
        P[i] = int(input_data[idx]); idx += 1
    
    queries = []
    for j in range(Q):
        S = int(input_data[idx]); idx += 1
        K = int(input_data[idx]); idx += 1
        queries.append((S, K))
    
    # For each query (S, K), starting at S, we record digits K times.
    # V = d_1 * 10^(K-1) + d_2 * 10^(K-2) + ... + d_K * 10^0
    # 
    # We can think of this as: V = 0, then for each step: V = V * 10 + d_current, then move.
    # So the state is (current_node, V_mod_M).
    # But V_mod_M can be up to 10^9, so we can't track it directly.
    #
    # Instead, we use the functional graph structure.
    # After K steps from node S:
    #   Let node_0 = S, node_1 = P[node_0], ..., node_{t} = P[node_{t-1}]
    #   V = D[node_0] * 10^{K-1} + D[node_1] * 10^{K-2} + ... + D[node_{K-1}] * 10^0
    #
    # We can use doubling. Define for each node u and power 2^k:
    #   jump[k][u] = the node reached after 2^k steps from u
    #   val[k][u] = the value (mod M) of the digit string collected in those 2^k steps
    #   pow10[k] = 10^(2^k) mod M
    #
    # If we concatenate two segments of lengths A and B (A first, then B):
    #   combined_val = val_A * 10^B + val_B
    #
    # Base case (k=0, 1 step):
    #   jump[0][u] = P[u]
    #   val[0][u] = D[u] % M
    #   pow10[0] = 10 % M  (since length is 1, 10^1... wait)
    #
    # Actually, if segment has length L, and its value is V, then concatenating segment1 (length L1, value V1) 
    # followed by segment2 (length L2, value V2): combined = V1 * 10^L2 + V2, length = L1 + L2.
    #
    # For 2^k steps:
    #   pow10[k] = 10^(2^k) mod M  -- this is the "shift" factor for a segment of length 2^k
    #   jump[k][u] = jump[k-1][jump[k-1][u]]
    #   val[k][u] = (val[k-1][u] * pow10[k-1] + val[k-1][jump[k-1][u]]) % M
    
    MAXLOG = 61  # since K can be up to 10^18
    
    jump = [[0] * (N + 1) for _ in range(MAXLOG)]
    val = [[0] * (N + 1) for _ in range(MAXLOG)]
    pow10 = [0] * MAXLOG
    
    # Base case: k = 0, 1 step
    pow10[0] = 10 % M
    for u in range(1, N + 1):
        jump[0][u] = P[u]
        val[0][u] = D[u] % M
    
    # Build doubling table
    for k in range(1, MAXLOG):
        pow10[k] = pow10[k-1] * pow10[k-1] % M
        for u in range(1, N + 1):
            mid = jump[k-1][u]
            jump[k][u] = jump[k-1][mid]
            val[k][u] = (val[k-1][u] * pow10[k-1] + val[k-1][mid]) % M
    
    out = []
    for S, K in queries:
        if K == 0:
            out.append(str(0 % M))
            continue
        
        cur_node = S
        cur_val = 0
        cur_len = 0  # accumulated length so far (for shift computation)
        
        # Process bits from high to low
        for k in range(MAXLOG - 1, -1, -1):
            if K >> k & 1:
                # Append segment of length 2^k starting from cur_node
                # new_val = cur_val * 10^(2^k) + val[k][cur_node]
                cur_val = (cur_val * pow10[k] + val[k][cur_node]) % M
                cur_node = jump[k][cur_node]
        
        out.append(str(cur_val % M))
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

この解説は claude4.6opus-thinking によって生成されました。