結果

問題 No.148 試験監督(3)
ユーザー lam6er
提出日時 2025-04-15 23:36:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,422 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 73,884 KB
最終ジャッジ日時 2025-04-15 23:37:31
合計ジャッジ時間 4,501 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #

MOD = 10**9 + 7
MOD_STR = str(MOD)
MOD_LEN = len(MOD_STR)

def multiply_by_two(s):
    result = []
    carry = 0
    for c in reversed(s):
        digit = int(c)
        total = digit * 2 + carry
        carry = total // 10
        result.append(str(total % 10))
    if carry > 0:
        result.append(str(carry))
    return ''.join(reversed(result))

def subtract_one(s):
    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:
        return ''.join(digits).lstrip('0') or '0'
    return ''.join(digits)

def compare_strings(a, b):
    if len(a) > len(b):
        return True
    elif len(a) < len(b):
        return False
    else:
        for i in range(len(a)):
            if a[i] > b[i]:
                return True
            elif a[i] < b[i]:
                return False
        return True

def is_p_ge_mod(p_str):
    if len(p_str) > MOD_LEN:
        return True
    elif len(p_str) < MOD_LEN:
        return False
    else:
        for i in range(MOD_LEN):
            p_digit = int(p_str[i])
            mod_digit = int(MOD_STR[i])
            if p_digit > mod_digit:
                return True
            elif p_digit < mod_digit:
                return False
        return True

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

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    idx = 1
    for _ in range(T):
        C_str = input[idx]
        P_str = input[idx + 1]
        idx += 2
        
        twoP = multiply_by_two(P_str)
        twoP_minus_1 = subtract_one(twoP)
        
        if not compare_strings(C_str, twoP_minus_1):
            print(0)
            continue
        
        if is_p_ge_mod(P_str):
            print(0)
            continue
        
        P_num = int(P_str)
        C_mod = mod_str(C_str, MOD)
        P_mod = mod_str(P_str, MOD)
        
        k = (C_mod - P_mod + 1) % MOD
        if k < 0:
            k += MOD
        
        if k < P_num:
            print(0)
            continue
        
        product = 1
        for i in range(P_num):
            product = product * (k - i) % MOD
        
        print(product % MOD)

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