結果

問題 No.148 試験監督（3）
ユーザー gew1fw
提出日時 2025-06-12 21:32:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,356 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 76,240 KB
最終ジャッジ日時 2025-06-12 21:33:16
合計ジャッジ時間 4,719 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7
MOD_str = '1000000007'

def double(s):
    res = []
    carry = 0
    for c in reversed(s):
        d = int(c)
        product = d * 2 + carry
        carry = product // 10
        res.append(product % 10)
    if carry > 0:
        res.append(carry)
    res = res[::-1]
    return ''.join(map(str, res)) if res else '0'

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

def is_ge(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 compute_mod(s, mod):
    result = 0
    for c in s:
        result = (result * 10 + int(c)) % mod
    return result

T = int(input())
for _ in range(T):
    C, P = input().split()
    
    # Check if P >= MOD
    p_ge = False
    if len(P) > len(MOD_str):
        p_ge = True
    elif len(P) == len(MOD_str):
        for i in range(len(P)):
            if P[i] > MOD_str[i]:
                p_ge = True
                break
            elif P[i] < MOD_str[i]:
                break
        else:
            p_ge = True
    if p_ge:
        print(0)
        continue
    
    # Compute 2P -1
    double_p = double(P)
    two_p_minus_1 = subtract_one(double_p)
    if not is_ge(C, two_p_minus_1):
        print(0)
        continue
    
    # Compute mod_c and mod_p
    mod_c = compute_mod(C, MOD)
    mod_p = compute_mod(P, MOD)
    
    k = int(P)
    
    # Compute combination(n, k) mod MOD
    result = 1
    for i in range(1, k+1):
        term = (mod_c - 2 * mod_p + 1 + i) % MOD
        term = (term + MOD) % MOD  # Ensure it's positive
        inv_i = pow(i, MOD-2, MOD)
        result = (result * term) % MOD
        result = (result * inv_i) % MOD
    
    # Compute P! mod MOD
    fact_p = 1
    for i in range(1, k+1):
        fact_p = (fact_p * i) % MOD
    
    total = (result * fact_p) % MOD
    print(total)
0