結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー lam6er
提出日時 2025-04-16 01:05:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,947 bytes
コンパイル時間 594 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 93,836 KB
最終ジャッジ日時 2025-04-16 01:07:41
合計ジャッジ時間 14,015 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 55 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

# Precompute the lengths of f(K) string representations for K up to 61
len_cache = [0] * 62
len_cache[1] = 1
for K in range(2, 62):
    mid = str(K * K)
    len_cache[K] = 2 * len_cache[K-1] + len(mid)

def get_sum_product(K, L, R):
    if L > R:
        return (0, 1)
    if K == 1:
        if L <= 1 <= R:
            return (1, 1)
        else:
            return (0, 1)
    
    len_prev = len_cache[K-1]
    mid_str = str(K * K)
    len_mid = len(mid_str)
    mid_start = len_prev + 1
    mid_end = len_prev + len_mid
    right_start = mid_end + 1
    
    # Calculate contributions from left part
    left_L = max(L, 1)
    left_R = min(R, len_prev)
    s_left, p_left = get_sum_product(K-1, left_L, left_R)
    
    # Calculate contributions from middle part
    s_mid = 0
    p_mid = 1
    mid_L = max(L, mid_start)
    mid_R = min(R, mid_end)
    if mid_L <= mid_R:
        start = mid_L - mid_start
        end = mid_R - mid_start
        for i in range(start, end + 1):
            c = mid_str[i]
            val = 10 if c == '0' else int(c)
            s_mid += val
            p_mid = (p_mid * val) % MOD
    
    # Calculate contributions from right part
    right_L = max(L, right_start)
    right_R = min(R, len_cache[K])
    new_L = right_L - (len_prev + len_mid) if right_L >= right_start else 0
    new_R = right_R - (len_prev + len_mid) if right_R >= right_start else 0
    s_right, p_right = get_sum_product(K-1, new_L, new_R)
    
    total_s = s_left + s_mid + s_right
    total_p = (p_left * p_mid) % MOD
    total_p = (total_p * p_right) % MOD
    
    return (total_s, total_p)

# Read input
K, L, R = map(int, input().split())

# Adjust K to 61 if it's larger, since len(K) for K>61 exceeds 1e18
if K > 61:
    K = 61

# Check if R exceeds the length of the string for K
if R > len_cache[K]:
    print(-1)
else:
    sum_total, product_total = get_sum_product(K, L, R)
    print(sum_total, product_total)
0