Overview

This problem involves walking on a functional graph (a graph where each node has out-degree 1), recording digits along the way, interpreting them as a decimal number, and finding the remainder when divided by \(M\). Since the number of operations \(K\) can be as large as \(10^{18}\), we use doubling (preprocessing similar to repeated squaring) to handle this efficiently.

Analysis

Organizing the Value Computation Formula

Starting from terminal \(S\), let the terminals visited in \(K\) operations be \(u_0, u_1, \ldots, u_{K-1}\) (where \(u_0 = S\), \(u_{t+1} = P_{u_t}\)). The resulting value is:

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

This is equivalent to “appending one digit at a time to the right.” In other words, if we compute \(V\) incrementally:

\[V \leftarrow V \times 10 + D[\text{current terminal}]\]

repeated \(K\) times would suffice, but since \(K\) can be up to \(10^{18}\), this would result in TLE.

Problem with the Naive Approach

Simulating one step at a time takes \(O(K)\), which is far too slow for \(K \leq 10^{18}\).

Key Insight: Concatenation of Intervals

When concatenating an interval of length \(L_1\) (with value \(V_1\)) and an interval of length \(L_2\) (with value \(V_2\)):

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

Using this property, we can manage information for \(2^k\) steps at once with doubling.

Algorithm

Building the Doubling Table

For each node \(u\) and each \(k = 0, 1, \ldots, 60\), we precompute the following:

• \(\text{jump}[k][u]\): the node reached after \(2^k\) steps from node \(u\)
• \(\text{val}[k][u]\): the value of the digit sequence from \(2^k\) steps starting at node \(u\), interpreted as a decimal number (\(\bmod M\))
• \(\text{pow10}[k] = 10^{2^k} \bmod M\)

Initialization (\(k = 0\), 1 step): - \(\text{jump}[0][u] = P[u]\) - \(\text{val}[0][u] = D[u] \bmod M\) - \(\text{pow10}[0] = 10 \bmod M\)

Transition (\(k \geq 1\)):

\(2^k\) steps can be decomposed into the first \(2^{k-1}\) steps + the second \(2^{k-1}\) steps.

• \(\text{mid} = \text{jump}[k-1][u]\) (the node reached after the first half)
• \(\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\)

Query Processing

Expand \(K\) in binary, and for each set bit at position \(k\), concatenate the interval corresponding to \(2^k\) steps from the most significant bit to the least significant bit.

As a concrete example, for \(K = 5 = (101)_2\): 1. First, process the \(2^2 = 4\) step interval 2. Then, append the \(2^0 = 1\) step interval

When concatenating:

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

then update \(\text{cur\_node}\) to \(\text{jump}[k][\text{cur\_node}]\).

Complexity

• Time complexity: \(O(N \log K_{\max} + Q \log K_{\max})\) (\(O(N \log K_{\max})\) for preprocessing, \(O(\log K_{\max})\) per query)
• Space complexity: \(O(N \log K_{\max})\) (for storing the doubling table)

Here \(\log K_{\max} \approx 61\).

Implementation Notes

• Special handling for \(K = 0\): If no operations are performed, \(V = 0\), so output \(0 \bmod M\).

• Processing bits from most significant to least: Since interval concatenation is “appending to the end” rather than “prepending to the front,” processing from the most significant bit of \(K\) allows us to accumulate intervals in the correct order.

• Case \(M = 1\): All answers become \(0\), but this is naturally handled by % M in the code.

• Memory efficiency: Due to the constraint \(N + Q \leq 1.5 \times 10^5\), when \(N\) is large, \(Q\) is small, so the overall size of the doubling table fits appropriately.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.