結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:39:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,249 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 83,756 KB
最終ジャッジ日時 2025-03-31 17:41:05
合計ジャッジ時間 33,160 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39 TLE * 17 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def get_len(n):
    return len(str(n * n))

# Precompute S(n) for n up to a certain point where S(n) exceeds 1e18
max_n = 60
S = [0] * (max_n + 2)
len_n2 = [0] * (max_n + 2)
S[1] = 1
len_n2[1] = 1  # len(1^2)

for k in range(2, max_n + 1):
    len_n2[k] = get_len(k)
    S[k] = 2 * S[k - 1] + len_n2[k]

def get_S(n):
    # If n is larger than our precomputed max, assume S(n) is huge
    if n > max_n:
        return float('inf')
    return S[n]

def find_k_th_digit(n, x):
    if x <= 0:
        return 0  # invalid
    while True:
        if n == 1:
            return 1 if x == 1 else -1
        # Compute S(n-1) and len(n^2)
        sn_prev = get_S(n-1)
        if sn_prev == float('inf'):
            # if n-1 is beyond precomputed, check if x is in the mid part
            # but mid part is len(str(n*n)), so check if x is small enough to be in the mid
            current_len_n2 = get_len(n)
            if x <= current_len_n2:
                return int(str(n*n)[x-1])
            else:
                # consider it as part of the prev structure, but since sn_prev is inf, we can't proceed
                # thus, decrease n
                n -= 1
                continue
        len_mid = get_len(n)
        if x <= sn_prev:
            n -= 1
            continue
        elif x <= sn_prev + len_mid:
            pos_in_mid = x - sn_prev
            return int(str(n*n)[pos_in_mid - 1])
        else:
            x -= (sn_prev + len_mid)
            n -= 1

def compute_total_length(k):
    if k <= max_n:
        return S[k]
    return float('inf')

def solve():
    import sys
    K, L, R = map(int, sys.stdin.readline().split())
    total_length = compute_total_length(K)
    if R > total_length:
        print(-1)
        return

    sum_val = 0
    product_val = 1

    for x in range(L, R + 1):
        digit = find_k_th_digit(K, x)
        if digit == -1:
            print(-1)
            return
        # Convert 0 to 10 for sum and product
        if digit == 0:
            sum_val += 10
            product_val = (product_val * 10) % MOD
        else:
            sum_val += digit
            product_val = (product_val * digit) % MOD
    print(sum_val, product_val)

if __name__ == '__main__':
    solve()
0