結果
| 問題 |
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 |
ソースコード
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()