結果

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

ソースコード

diff # 

import sys

def main():
    MOD = 10**9 + 7
    K, L, R = map(int, sys.stdin.readline().split())

    # Precompute S(k) for k up to 60
    def compute_S(k):
        s = 0
        for m in range(1, k + 1):
            d = len(str(m * m))
            exponent = k - m
            s += d * (1 << exponent)
        return s

    # Determine if K is small (<=60) or large
    if K <= 60:
        S_k = compute_S(K)
        if R > S_k:
            print(-1)
            return
    else:
        if R > 10**18:
            print(-1)
            return
        # Compute current_K as min(K, R.bit_length())
        current_K = min(K, R.bit_length())
        S_k = compute_S(current_K)
        if R > S_k:
            print(-1)
            return
        K = current_K

    # Precompute S values for all k up to K
    S_cache = [0] * (K + 1)
    for k in range(1, K + 1):
        S_cache[k] = compute_S(k)

    sum_total = 0
    product_total = 1

    def process(k, l, r):
        nonlocal sum_total, product_total
        if l > r:
            return
        if k == 1:
            if l <= 1 and r >= 1:
                sum_total += 1
                product_total = (product_total * 1) % MOD
            return

        len_left = S_cache[k - 1]
        len_middle = len(str(k * k))
        start_middle = len_left + 1
        end_middle = len_left + len_middle
        end_right = 2 * len_left + len_middle

        # Check if entirely in left part
        if r <= len_left:
            process(k - 1, l, r)
            return
        # Check if entirely in right part
        if l > end_middle:
            new_l = l - end_middle
            new_r = r - end_middle
            process(k - 1, new_l, new_r)
            return

        # Process left part
        if l <= len_left:
            part_r = min(r, len_left)
            process(k - 1, l, part_r)
            l = part_r + 1
            if l > r:
                return

        # Process middle part
        if l <= end_middle and r >= start_middle:
            part_l = max(l, start_middle)
            part_r = min(r, end_middle)
            digits = str(k * k)
            start = part_l - start_middle
            end = part_r - start_middle
            for i in range(start, end + 1):
                digit = int(digits[i])
                if digit == 0:
                    sum_total += 10
                    product_total = (product_total * 10) % MOD
                else:
                    sum_total += digit
                    product_total = (product_total * digit) % MOD
            l = part_r + 1
            if l > r:
                return

        # Process right part
        if l <= r:
            new_l = l - end_middle
            new_r = r - end_middle
            process(k - 1, new_l, new_r)

    process(K, L, R)
    print(sum_total, product_total % MOD)

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