結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー gew1fw
提出日時 2025-06-12 16:45:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,030 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 97,076 KB
最終ジャッジ日時 2025-06-12 16:45:32
合計ジャッジ時間 14,980 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 55 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

# Precompute len_dict for n up to 70
len_dict = {1: 1}
max_n = 1
while True:
    max_n += 1
    prev_len = len_dict[max_n - 1]
    n_squared = max_n * max_n
    len_middle = len(str(n_squared))
    new_len = 2 * prev_len + len_middle
    len_dict[max_n] = new_len
    if new_len > 10**18:
        break
    if max_n > 70:
        break

def compute(n, a, b):
    if a > b:
        return (0, 1, True)
    if n == 1:
        if a == 1 and b == 1:
            return (1, 1, True)
        else:
            return (0, 1, False)
    len_left = len_dict.get(n-1, 0)
    len_middle = len(str(n * n))
    len_right = len_left
    total_len = 2 * len_left + len_middle
    if a > total_len or b > total_len:
        return (0, 1, False)
    left_end = len_left
    middle_start = left_end + 1
    middle_end = left_end + len_middle
    right_start = middle_end + 1
    right_end = total_len
    res_sum = 0
    res_prod = 1
    i = a
    while i <= b:
        if i <= left_end:
            part_start = i
            part_end = min(b, left_end)
            sum_val, prod_val, valid = compute(n-1, part_start, part_end)
            if not valid:
                return (0, 1, False)
            res_sum += sum_val
            res_prod = (res_prod * prod_val) % MOD
            i = part_end + 1
        elif i <= middle_end:
            part_start = i
            part_end = min(b, middle_end)
            s = str(n * n)
            start_pos = part_start - left_end - 1
            end_pos = part_end - left_end - 1
            if start_pos < 0 or end_pos >= len(s):
                return (0, 1, False)
            substr = s[start_pos:end_pos+1]
            sum_middle = 0
            prod_middle = 1
            for c in substr:
                if c == '0':
                    val = 10
                else:
                    val = int(c)
                sum_middle += val
                prod_middle = (prod_middle * val) % MOD
            res_sum += sum_middle
            res_prod = (res_prod * prod_middle) % MOD
            i = part_end + 1
        else:
            part_start = i
            part_end = min(b, right_end)
            local_start = part_start - right_start + 1
            local_end = part_end - right_start + 1
            sum_val, prod_val, valid = compute(n-1, local_start, local_end)
            if not valid:
                return (0, 1, False)
            res_sum += sum_val
            res_prod = (res_prod * prod_val) % MOD
            i = part_end + 1
    return (res_sum, res_prod, True)

def main():
    import sys
    K, L, R = map(int, sys.stdin.readline().split())
    if L > R:
        print(-1)
        return
    if K <= 70:
        len_K = len_dict.get(K, 0)
        if len_K < R:
            print(-1)
            return
    else:
        if R > 10**18:
            print(-1)
            return
    sum_total, prod_total, valid = compute(K, L, R)
    if not valid:
        print(-1)
    else:
        print(sum_total, prod_total % MOD)

if __name__ == "__main__":
    main()
0