結果

問題 No.148 試験監督（3）
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:17:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,350 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,800 KB
実行使用メモリ 74,884 KB
最終ジャッジ日時 2025-05-14 13:18:45
合計ジャッジ時間 4,713 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set the modulus
M = 10**9 + 7

def solve():
    # Read C and P as strings
    C_str, P_str = sys.stdin.readline().split()

    # Compare P with M using string representation because P can be very large
    M_str = str(M)
    P_len = len(P_str)
    M_len = len(M_str)
    
    P_ge_M = False
    if P_len > M_len:
        # If P has more digits than M, P >= M
        P_ge_M = True
    elif P_len == M_len:
        # If P has same number of digits as M, compare lexicographically
        if P_str >= M_str:
            P_ge_M = True

    # If P >= M, the number of ways involves P! which is 0 mod M (since M is prime)
    # Or equivalently, the product P(N, P) = N * (N-1) * ... * (N-P+1)
    # contains P terms. If P >= M, this sequence of P consecutive integers (or their residues mod M)
    # must contain a multiple of M. Thus the product is 0 mod M.
    if P_ge_M:
        print(0)
        return

    # P is small enough to be < M. Convert P to integer p.
    # Note: Python's int() handles arbitrary precision integers automatically.
    # Here p is guaranteed to be less than M=10^9+7, so it fits within standard 64-bit integer types.
    p = int(P_str)

    # If p = 0, there are no students to place. There is exactly 1 way to do this (empty placement).
    if p == 0:
        print(1)
        return

    # Use Python's arbitrary precision integers for C value
    C_val = int(C_str)
    # P_val = p for clarity, using the integer value from now on
    P_val = p 

    # Check the condition for impossibility: C+1 < 2P.
    # This means there are not enough chairs to place P students non-adjacently.
    # The minimum number of chairs required is P (for students) + (P-1) (for gaps) = 2P-1.
    # So we need C >= 2P - 1, which is equivalent to C+1 >= 2P.
    # If C+1 < 2P, it's impossible.
    if C_val + 1 < 2 * P_val:
        print(0)
        return

    # Calculate N = C - P + 1, which is the number of items to choose from in the stars and bars formulation.
    # We need N mod M. We can calculate this using modular arithmetic properties.
    # N mod M = (C - P + 1) mod M = (C mod M - P mod M + 1 mod M) mod M
    
    # Compute C_mod = C % M iteratively from the string representation of C.
    # This avoids creating potentially huge C_val if only C_mod is needed later.
    C_mod = 0
    for digit in C_str:
        C_mod = (C_mod * 10 + int(digit)) % M

    # Compute N_mod = N % M
    # Since P_val = p < M, P_val % M is just P_val.
    N_mod = (C_mod - P_val + 1) % M
    # Ensure N_mod is non-negative (Python's % might return negative for negative dividend)
    # Although (X % M + M) % M is the safer way, Python's % for positive M already gives result in [0, M-1] or [-(M-1), 0].
    # Test: (-1) % 10 = 9.  (-11) % 10 = 9. Looks like it works correctly for positive M.
    # To be absolutely safe:
    if N_mod < 0:
        N_mod += M
    
    # The number of ways is P(N, P) = N * (N-1) * ... * (N-P+1).
    # We need P(N, P) mod M.
    # If any term N-i (for 0 <= i < P) is divisible by M, the product is 0 mod M.
    # This happens if N = i mod M for some 0 <= i < P.
    # This is equivalent to N_mod = N % M being in the range {0, 1, ..., P-1}.
    # So, if N_mod < p, the result is 0.
    if N_mod < p:
        print(0)
        return

    # If N_mod >= p, then none of the terms N, N-1, ..., N-P+1 are divisible by M.
    # In this case, P(N, P) mod M = (N mod M * (N-1) mod M * ... * (N-P+1) mod M) mod M
    # This simplifies to P(N_mod, p) = N_mod * (N_mod-1) * ... * (N_mod - p + 1) mod M.
    # We compute this product iteratively.
    
    result = 1
    # Calculate the product N_mod * (N_mod-1) * ... * (N_mod - p + 1) mod M
    for i in range(p):
        # Calculate term (N_mod - i)
        term = (N_mod - i)
        # Since N_mod >= p, for i <= p-1, N_mod - i >= p - (p-1) = 1.
        # So all terms are positive integers.
        # Multiply into result and take modulo M
        result = (result * term) % M

    # Final result should be in [0, M-1]. Python's % operator ensures this for positive modulus.
    # Just in case intermediate computations yield negative temporary results (though unlikely here)
    if result < 0:
         result += M

    print(result)


# Read the number of test cases
T = int(sys.stdin.readline())
# Process each test case
for _ in range(T):
    solve()
0