結果
問題 |
No.148 試験監督(3)
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()