結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String)
ユーザー qwewe
提出日時 2025-05-14 13:06:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 47 ms / 800 ms
コード長 8,866 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,796 KB
実行使用メモリ 58,368 KB
最終ジャッジ日時 2025-05-14 13:07:19
合計ジャッジ時間 7,287 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

# Increase recursion depth limit for safety, although the maximum depth needed (61) is typically well below default limits.
# sys.setrecursionlimit(2000) 

MOD = 1000000007

# Global dictionary for memoization of query results to avoid redundant computations.
memo_query = {}

# Global dictionary to store precomputed lengths of S(k) for k up to 61.
precomputed_lengths = {} 
# A sentinel value slightly larger than the maximum possible R (10^18)
# to indicate that the actual length exceeds 10^18.
MAX_LEN = 10**18 + 1 

def precompute():
    """
    Precomputes the lengths of S(k) for k from 0 up to 61.
    Stores lengths in the global `precomputed_lengths` dictionary.
    If a length exceeds 10^18, it's stored as MAX_LEN.
    This function is idempotent; it computes lengths only once.
    """
    global precomputed_lengths
    # Check if already computed to avoid redundant work
    if 0 in precomputed_lengths: 
        return
        
    precomputed_lengths[0] = 0
    precomputed_lengths[1] = 1
    for k in range(2, 62): # Compute lengths up to k=61
        # Get length of S(k-1)
        prev_len = precomputed_lengths[k-1]
        
        # If S(k-1)'s length already exceeds the threshold, S(k)'s length will too.
        if prev_len >= MAX_LEN:
             precomputed_lengths[k] = MAX_LEN
             continue
        
        # Calculate k*k. Use integer type which supports large numbers.
        k_val = k 
        k_squared = k_val * k_val
        
        # Calculate the number of digits in k^2. Standard library functions are efficient enough.
        dk2 = len(str(k_squared)) 
        
        # Calculate the length of S(k) using the recursive formula: |S(k)| = 2*|S(k-1)| + d(k^2)
        # Python's integers handle arbitrary precision, avoiding overflow issues.
        new_len = 2 * prev_len + dk2 
        
        # If the calculated length exceeds 10^18, store the sentinel value MAX_LEN.
        if new_len > 10**18:
            precomputed_lengths[k] = MAX_LEN
        else:
            # Otherwise, store the exact computed length.
            precomputed_lengths[k] = new_len

def query_middle(k, l, r):
    """
    Computes the sum and product of digits within the specified range [l, r] (1-based indices)
    of the string representation of k^2. 
    Implements the special rule where digit '0' is treated as 10 for calculations.
    Product is computed modulo MOD.
    """
    k_val = k
    k_squared = k_val * k_val
    sN = str(k_squared) # Convert k^2 to string to access its digits.
    
    # Extract the relevant substring using 0-based indexing for Python slicing.
    # The range [l, r] is 1-based, so slice is sN[l-1 : r].
    sub = sN[l-1 : r]

    current_sum = 0
    current_prod = 1
    
    for digit_char in sub:
        digit = int(digit_char)
        # Apply the special rule for '0'.
        if digit == 0:
             val = 10
        else:
             val = digit
        # Accumulate sum.
        current_sum += val
        # Accumulate product modulo MOD.
        current_prod = (current_prod * val) % MOD
        
    return (current_sum, current_prod)


def query(k, l, r):
    """
    Recursively computes the sum and product of digits for the range [l, r] (1-based indices) within S(k).
    Uses memoization (`memo_query`) to store and retrieve results for state (k, l, r),
    significantly speeding up computation by avoiding recalculations.
    Handles the recursive structure S(k) = S(k-1) + str(k^2) + S(k-1).
    """
    # Create state tuple for memoization lookup.
    state = (k, l, r)
    # Return cached result if available.
    if state in memo_query: 
        return memo_query[state]

    # Base cases for recursion:
    # If range is invalid (l > r) or k=0 (empty sequence), return sum 0, product 1.
    if l > r or k == 0:
        return (0, 1)
    
    # Base case k=1: S(1) = "1".
    if k == 1:
        # Check if the single digit at index 1 is within the query range [l, r].
        if l <= 1 <= r:
            result = (1, 1) # Sum 1, Product 1.
        else:
            result = (0, 1) # Index 1 is outside range. Sum 0, Product 1.
        # Memoize the result for this base case state.
        memo_query[state] = result
        return result

    # Recursive step for k > 1:
    
    # Get the precomputed length of S(k-1).
    len_k_minus_1 = precomputed_lengths[k-1]
    
    # Calculate k^2 and its number of digits d(k^2).
    k_val = k
    k_squared = k_val * k_val
    dk2 = len(str(k_squared))

    # Initialize total sum and product for the current query range.
    total_sum = 0
    total_prod = 1

    # Process the three parts of S(k): S(k-1), str(k^2), S(k-1)

    # Part 1: Intersection with the first S(k-1) component (indices [1, len_k_minus_1])
    l1 = max(l, 1)
    # Determine the correct upper bound r1 for the intersection.
    # If len_k_minus_1 is MAX_LEN, true length is > 10^18. Since r <= 10^18, min(r, true_len) = r.
    # If len_k_minus_1 < MAX_LEN, it's the exact length. Use min(r, len_k_minus_1).
    r1 = min(r, len_k_minus_1) if len_k_minus_1 < MAX_LEN else r
    
    # If the intersection range [l1, r1] is valid:
    if l1 <= r1:
        # Recursively call query for the relevant part of S(k-1).
        res1_sum, res1_prod = query(k-1, l1, r1)
        # Combine results.
        total_sum = (total_sum + res1_sum) # Sum accumulates normally.
        total_prod = (total_prod * res1_prod) % MOD # Product accumulates modulo MOD.

    # Part 2: Intersection with the middle str(k^2) component (indices [len_k_minus_1 + 1, len_k_minus_1 + dk2])
    # This middle part computation is only needed if its start index is potentially within R's bounds.
    # This requires len_k_minus_1 to be less than MAX_LEN (i.e., actual length <= 10^18).
    if len_k_minus_1 < MAX_LEN:
        middle_start = len_k_minus_1 + 1
        middle_end = len_k_minus_1 + dk2
        
        l2 = max(l, middle_start)
        r2 = min(r, middle_end)
      
        # If the intersection range [l2, r2] is valid:
        if l2 <= r2:
            # Call query_middle for the relevant digits of str(k^2).
            # Adjust indices to be 1-based relative to the start of str(k^2).
            res2_sum, res2_prod = query_middle(k, l2 - len_k_minus_1, r2 - len_k_minus_1)
            # Combine results.
            total_sum = (total_sum + res2_sum)
            total_prod = (total_prod * res2_prod) % MOD

        # Part 3: Intersection with the second S(k-1) component (indices [len_k_minus_1 + dk2 + 1, |S(k)|])
        second_part_start = len_k_minus_1 + dk2 + 1
        # Get the total length of S(k), which might be MAX_LEN.
        len_k = precomputed_lengths[k] 
        
        l3 = max(l, second_part_start)
        # Determine the correct upper bound r3 for the intersection.
        # Logic similar to r1: if len_k is MAX_LEN, effective upper bound is r. Otherwise min(r, len_k).
        r3 = min(r, len_k) if len_k < MAX_LEN else r

        # If the intersection range [l3, r3] is valid:
        if l3 <= r3:
            # Calculate the offset to convert absolute indices [l3, r3] to relative indices for S(k-1).
            offset = len_k_minus_1 + dk2
            # Recursively call query for the relevant part of the second S(k-1).
            res3_sum, res3_prod = query(k-1, l3 - offset, r3 - offset)
            # Combine results.
            total_sum = (total_sum + res3_sum)
            total_prod = (total_prod * res3_prod) % MOD

    # Memoize the computed result for the state (k, l, r) before returning.
    memo_query[state] = (total_sum, total_prod)
    return (total_sum, total_prod)

# Main execution logic
def solve():
    # Read input values K, L, R.
    K, L, R = map(int, sys.stdin.readline().split())

    # Precompute lengths up to k=61.
    precompute()

    # Determine the effective K to use for the query.
    # Since S(k) for k > 61 starts with S(61), and L, R <= 10^18 < |S(61)|,
    # any query on S(k) for k > 61 within range [L, R] is equivalent to a query on S(61).
    effective_K = min(K, 61)
    
    # Get the length of S(effective_K) to check against R.
    length_to_check = precomputed_lengths[effective_K]

    # Check if R exceeds the length of S(effective_K).
    # This check is only necessary if the length is known exactly (not capped at MAX_LEN).
    # If length_to_check is MAX_LEN, it means actual length > 10^18, so R is always within bounds.
    if length_to_check < MAX_LEN and R > length_to_check:
         # If R is out of bounds, print -1 as required.
         print("-1")
    else:
         # If R is within bounds or the length is potentially larger than R, proceed with the query.
         final_sum, final_prod = query(effective_K, L, R)
         # Print the final computed sum and product.
         print(f"{final_sum} {final_prod}")

# Run the main solver function.
solve()
0