結果

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

ソースコード

diff #

MOD = 10**9 + 7
MOD_STR = "1000000007"

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

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)
    new_s = ''.join(digits).lstrip('0')
    return new_s if new_s else '0'

def compare_strings(a, b):
    if len(a) > len(b):
        return True
    elif len(a) < len(b):
        return False
    else:
        return a >= b

def is_p_ge_mod(p_str):
    if len(p_str) > len(MOD_STR):
        return True
    elif len(p_str) < len(MOD_STR):
        return False
    else:
        return p_str >= MOD_STR

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

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
        
        # Step 1: Compute 2P - 1 as strings
        two_p = multiply_by_2(P_str)
        two_p_minus_1 = subtract_one(two_p)
        
        # Check if C >= 2P - 1
        if not compare_strings(C_str, two_p_minus_1):
            print(0)
            continue
        
        # Check if P >= MOD
        if is_p_ge_mod(P_str):
            print(0)
            continue
        
        P_val = int(P_str)
        C_mod = mod_of_large_number(C_str, MOD)
        P_mod = mod_of_large_number(P_str, MOD)
        
        n_mod = (C_mod - P_mod + 1) % MOD
        if n_mod < 0:
            n_mod += MOD
        
        # Compute permutation(n_mod, P_val) mod MOD
        result = 1
        for i in range(P_val):
            term = (n_mod - i) % MOD
            result = (result * term) % MOD
        
        print(result)

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