結果
問題 |
No.148 試験監督(3)
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:38:08 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,091 bytes |
コンパイル時間 | 421 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 58,496 KB |
最終ジャッジ日時 | 2025-06-12 21:42:14 |
合計ジャッジ時間 | 6,701 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 2 -- * 10 |
ソースコード
MOD = 10**9 + 7 def compare_num_strings(a, b): if len(a) > len(b): return 1 elif len(a) < len(b): return -1 else: for i in range(len(a)): if a[i] > b[i]: return 1 elif a[i] < b[i]: return -1 return 0 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 == -1: return '-1' s_list[i] = str(int(s_list[i]) - 1) res = ''.join(s_list) if res[0] == '0' and len(res) > 1: res = res.lstrip('0') return res def multiply_by_two(s): res = [] carry = 0 for c in reversed(s): d = int(c) * 2 + carry carry = d // 10 res.append(d % 10) if carry > 0: res.append(carry) res = ''.join(map(str, reversed(res))) return res def add_one(s): s_list = list(s) i = len(s_list) - 1 while i >= 0: if s_list[i] == '9': s_list[i] = '0' i -= 1 else: s_list[i] = str(int(s_list[i]) + 1) break if i == -1: s_list = ['1'] + s_list return ''.join(s_list) def compute_2P_minus_1(P_str): two_p = multiply_by_two(P_str) two_p_minus_1 = subtract_one(two_p) return two_p_minus_1 def int_mod(s, mod): res = 0 for c in s: res = (res * 10 + int(c)) % mod return res def subtract_mod(A, B, mod): a_mod = int_mod(A, mod) b_mod = int_mod(B, mod) result = (a_mod - b_mod) % mod return result 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 # Condition a: P > C? cmp = compare_num_strings(P, C) if cmp == 1: print(0) continue # Compute 2P-1 and compare with C twoP_minus1 = compute_2P_minus_1(P) cmp_twoP_minus1 = compare_num_strings(C, twoP_minus1) if cmp_twoP_minus1 == -1: print(0) continue # Condition c: P >= MOD? if len(P) > len(str(MOD)): print(0) continue elif len(P) == len(str(MOD)): if compare_num_strings(P, str(MOD)) >= 0: print(0) continue # Condition d: C >= MOD? if len(C) > len(str(MOD)): print(0) continue elif len(C) == len(str(MOD)): if compare_num_strings(C, str(MOD)) >= 0: print(0) continue # Compute (C - P +1) mod MOD temp = subtract_mod(C, P, MOD) temp = (temp + 1) % MOD # Compute product product = 1 P_int = int(P) for k in range(P_int): term = (temp - k) % MOD if term < 0: term += MOD product = (product * term) % MOD print(product % MOD) if __name__ == "__main__": main()