結果
| 問題 |
No.493 とても長い数列と文字列(Long Long Sequence and a String）
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-20 20:39:23 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,802 bytes |
| コンパイル時間 | 171 ms |
| コンパイル使用メモリ | 82,188 KB |
| 実行使用メモリ | 80,376 KB |
| 最終ジャッジ日時 | 2025-03-20 20:39:44 |
| 合計ジャッジ時間 | 14,810 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 55 TLE * 1 -- * 59 |
ソースコード
MOD = 10**9 + 7
def main():
import sys
K, L, R = map(int, sys.stdin.readline().split())
# Precompute lengths len_k and s_k (digits of k^2)
# We need to compute len_k for all k up to K if K is manageable
# Also, precompute s_k and the digits of k^2 for k up to K
# Precompute the maximum K we might need to process for the sum/product part
# But since K can be up to 1e9, we need an alternative way to compute len(K)
# We first check whether len(K) >= R. If not, output -1
# To compute len(K), use the formula len(k) = 2*len(k-1) + s(k), where s(k) is the number of digits in k^2
# We'll compute len(k) if k is not very large, otherwise approximate
# First, compute max possible len(k) incrementally until it exceeds R or we reach K
# If K is large, like 1e9, and R is up to 1e18, len(k) = 2^(k) is way larger than 1e18
# So, for practical purposes, if k >= 60, len(k) > 1e18, but confirm for the given K and R
# Function to compute len(k), s(k), and digits of k^2
precomputed = []
max_k = 0
len_k = 0
s_k = 0
digits = []
# We need a way to compute len(k) incrementally, but K can be up to 1e9, which is impossible to precompute
# So, we need to compute len(k) recursively, and check if it's possible
# Alternatively, since len(k) grows exponentially, for k where 2^{k-1} > R, len(k) is obviously >= 2^{k-1} > R
# So, first compute 2^{k-1} and see if it's larger than R. Otherwise, compute len(k)
# But calculating 2^(k-1) for k=1e9 is impossible, so we need a mathematical approach
# So, we need to compute the minimal k where 2^{k-1} exceeds R, then if K >= that minimal k, len(K) > R
import math
def compute_min_k(R_val):
if R_val == 0:
return 0
return math.floor(math.log2(R_val)) + 2
minimal_k = compute_min_k(R)
if K >= minimal_k:
len_K_is_larger = True
else:
# Need to compute actual len(K)
# Compute len array up to K
len_array = [0] * (K + 1)
s_array = [0] * (K + 1)
digits_dict = {}
len_array[1] = 1
s_array[1] = 1
digits_dict[1] = ['1']
for k in range(2, K+1):
k_sq = k * k
s = len(str(k_sq))
s_array[k] = s
digits_dict[k] = list(map(int, str(k_sq)))
len_array[k] = 2 * len_array[k-1] + s
if len_array[k] > 1e18 * 2:
break # No need to compute further as it's beyond any possible R
len_K = len_array[K]
if len_K < R:
print(-1)
return
else:
len_K_is_larger = True
# Now, compute sum and product from L to R for f(K)
# We need a recursive approach to compute the digits
# Precompute len(k), s(k), digits for k up to a certain K (if K is small)
# Otherwise, K is up to 60 and R is up to 1e18
# However, for K up to 60, precompute necessary data
# Precompute necessary data (len, s, digits) for all k up to K
# Now compute data for all k from 1 to K
# Since K can be up to 1e9, but if K >= minimal_k (like 60), we can assume len(K) >= R
# So, handle cases where K < minimal_k, compute data up to K
# Compute len(k) for k up to minimal_k or K, whichever is smaller
max_k_to_compute = min(K, minimal_k)
len_array = []
s_array = []
digits_dict = {}
len_k = 0
for k in range(1, max_k_to_compute +1):
if k == 1:
len_k = 1
s_k_val = 1
digits = ['1']
else:
k_sq = k * k
s_k_val = len(str(k_sq))
digits = list(map(int, str(k_sq)))
len_k = 2 * len_array[k-1 -1] + s_k_val # assuming len_array is 0-based
len_array.append(len_k)
s_array.append(s_k_val)
digits_dict[k] = digits
# Now, compute if actual len(K) >= R
if K > max_k_to_compute:
# len(K) is definitely >= R
pass
else:
len_K_val = len_array[K-1] # assuming 0-based
if len_K_val < R:
print(-1)
return
# Now, process the range [L, R]
# We need a recursive function to compute the sum and product for positions in f(k)
memo = {}
def get_digits(k):
if k in digits_dict:
return digits_dict[k]
else:
k_sq = k * k
digits = list(map(int, str(k_sq)))
return digits
def compute_len(k):
if k == 0:
return 0
if k == 1:
return 1
if k <= len(len_array):
return len_array[k-1] # assuming len_array is 0-based for k starting 1
# else, compute using the recursive formula, but this is not feasible for large k
# however, this should not be necessary here since k <= max_k_to_compute
def helper(k, L, R):
if L > R:
return (0, 1)
if k == 1:
if L <=1 <= R:
return (1, 1)
else:
return (0, 1)
# Get len of f(k-1)
len_prev = compute_len(k-1)
s_k_val = len(str(k*k))
digits = get_digits(k)
mid_start = len_prev + 1
mid_end = len_prev + s_k_val
# Define regions:
a_L = L
a_R = min(R, len_prev)
left_sum = 0
left_prod = 1
if a_L <= a_R:
s, p = helper(k-1, a_L, a_R)
left_sum += s
left_prod = (left_prod * p) % MOD
mid_sum = 0
mid_prod = 1
b_L = max(L, mid_start)
b_R = min(R, mid_end)
if b_L <= b_R:
start_pos = b_L - mid_start
end_pos = b_R - mid_start
for i in range(start_pos, end_pos +1):
d = digits[i]
if d == 0:
mid_sum += 10
mid_prod = (mid_prod * 10) % MOD
else:
mid_sum += d
mid_prod = (mid_prod * d) % MOD
right_sum = 0
right_prod = 1
c_L = max(L, mid_end +1)
c_R = R
if c_L <= c_R:
offset = mid_end
new_L = c_L - offset
new_R = c_R - offset
s, p = helper(k-1, new_L, new_R)
right_sum += s
right_prod = (right_prod * p) % MOD
total_sum = left_sum + mid_sum + right_sum
total_prod = (left_prod * mid_prod) % MOD
total_prod = (total_prod * right_prod) % MOD
return (total_sum, total_prod)
# Since K might be larger than max_k_to_compute but minimal_k is small, adjust K to min(K, minimal_k)
effective_k = min(K, minimal_k)
sum_total, product_total = helper(effective_k, L, R)
print(sum_total, product_total % MOD)
if __name__ == '__main__':
main()