結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0