結果

問題 No.148 試験監督(3)
ユーザー lam6er
提出日時 2025-04-16 16:25:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,520 bytes
コンパイル時間 388 ms
コンパイル使用メモリ 81,652 KB
実行使用メモリ 74,640 KB
最終ジャッジ日時 2025-04-16 16:26:47
合計ジャッジ時間 4,798 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #

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

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

def multiply_two(s):
    carry = 0
    res = []
    for c in reversed(s):
        num = int(c)
        total = num * 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):
    s_list = list(s)
    i = len(s_list) - 1
    while i >= 0 and s_list[i] == '0':
        s_list[i] = '9'
        i -= 1
    if i < 0:
        return '0'
    s_list[i] = str(int(s_list[i]) - 1)
    if s_list[0] == '0' and len(s_list) > 1:
        return ''.join(s_list).lstrip('0') or '0'
    return ''.join(s_list)

def compute_2p_minus_1(p_str):
    two_p = multiply_two(p_str)
    return subtract_one(two_p)

def is_c_ge_2p_minus_1(c_str, p_str):
    two_p_minus_1 = compute_2p_minus_1(p_str)
    return str_ge(c_str, two_p_minus_1)

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

def p_factorial_mod(p_str, mod):
    if len(p_str) > len(mod_str_val):
        return 0
    elif len(p_str) == len(mod_str_val) and p_str >= mod_str_val:
        return 0
    else:
        p = int(p_str)
        res = 1
        for i in range(1, p+1):
            res = res * i % mod
        return res

def comb_mod(n, k, mod):
    if n < k or k < 0:
        return 0
    if k == 0:
        return 1
    numerator = 1
    for i in range(n, n - k, -1):
        numerator = numerator * i % mod
    denominator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod

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
        
        if not str_ge(C, P):
            print(0)
            continue
        
        if not is_c_ge_2p_minus_1(C, P):
            print(0)
            continue
        
        c_mod = mod_str(C, MOD)
        p_mod = mod_str(P, MOD)
        n_mod = (c_mod - p_mod + 1) % MOD
        
        if n_mod < p_mod:
            print(0)
            continue
        
        comb_val = comb_mod(n_mod, p_mod, MOD)
        p_fact = p_factorial_mod(P, MOD)
        ans = (comb_val * p_fact) % MOD
        print(ans)

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