結果

問題 No.148 試験監督(3)
ユーザー gew1fw
提出日時 2025-06-12 16:57:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,606 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 59,912 KB
最終ジャッジ日時 2025-06-12 16:57:22
合計ジャッジ時間 6,260 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other TLE * 2 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #

MOD = 10**9 + 7
MOD_str = str(MOD)

def compute_mod(s, mod):
    res = 0
    for c in s:
        res = (res * 10 + int(c)) % mod
    return res

def compare_strings(a, b):
    if len(a) > len(b):
        return 1
    elif len(a) < len(b):
        return -1
    else:
        if a == b:
            return 0
        elif a > b:
            return 1
        else:
            return -1

def multiply_string(s, factor):
    result = []
    carry = 0
    for c in reversed(s):
        digit = int(c)
        product = digit * factor + carry
        carry = product // 10
        result.append(product % 10)
    if carry > 0:
        result.append(carry)
    result_str = ''.join(reversed([str(d) for d in result]))
    return result_str

def multiply_string_by_2(s):
    return multiply_string(s, 2)

def subtract_one(s):
    if s == '0':
        return '0'
    digits = list(s)
    i = len(digits) - 1
    while i >= 0 and digits[i] == '0':
        digits[i] = '9'
        i -= 1
    if i < 0:
        return '0'
    digits[i] = str(int(digits[i]) - 1)
    if digits[0] == '0' and len(digits) > 1:
        digits = digits[1:]
    return ''.join(digits)

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    idx = 1
    for _ in range(T):
        C = input[idx]
        P = input[idx + 1]
        idx += 2
        
        # Check if P is >= MOD
        P_mod = compute_mod(P, MOD)
        if P_mod == 0:
            print(0)
            continue
        if len(P) > len(MOD_str):
            print(0)
            continue
        elif len(P) == len(MOD_str):
            if compare_strings(P, MOD_str) >= 0:
                print(0)
                continue
        
        # Check if C >= P
        cmp_result = compare_strings(C, P)
        if cmp_result < 0:
            print(0)
            continue
        
        # Check if C >= 2P - 1
        twoP = multiply_string_by_2(P)
        twoP_minus_1 = subtract_one(twoP)
        cmp_result = compare_strings(C, twoP_minus_1)
        if cmp_result < 0:
            print(0)
            continue
        
        # Compute n_mod = (C - P + 1) mod MOD
        C_mod = compute_mod(C, MOD)
        P_mod_val = compute_mod(P, MOD)
        n_mod = (C_mod - P_mod_val + 1 + MOD) % MOD
        
        # Check if n_mod >= P
        if n_mod < P_mod:
            print(0)
            continue
        
        # Compute the product
        product = 1
        for i in range(P_mod):
            term = (n_mod - i) % MOD
            product = (product * term) % MOD
        print(product)

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