結果

問題 No.1044 正直者大学
ユーザー qwewe
提出日時 2025-05-14 13:25:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 124 ms / 2,000 ms
コード長 3,684 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 65,172 KB
最終ジャッジ日時 2025-05-14 13:26:15
合計ジャッジ時間 3,030 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, M, K = map(int, sys.stdin.readline().split())
    MOD = 1_000_000_007

    # Determine max needed for factorial calculations
    if M == 0:
        max_idx_needed = N # For fact[N-1], need up to N-1 if N>0, or N if N is used directly.
                           # N-1 can be 0 if N=1. N can be up to 10^5.
                           # To be safe, if N-1 is used, fact table needs up to N-1.
                           # For fact[N-1], max index is N-1. Array size N.
                           # Let's make it simple: max index used is max(N, M).
    else:
        max_idx_needed = max(N, M)
    
    # max_idx_needed could be 0 if N=0, M=0. But N>=1. So min max_idx_needed is 1 (for N=1,M=0 or N=1,M=1).
    # Array of size max_idx_needed + 1 for indices 0 to max_idx_needed.
    
    fact = [1] * (max_idx_needed + 1)
    invfact = [1] * (max_idx_needed + 1)

    for i in range(1, max_idx_needed + 1):
        fact[i] = (fact[i-1] * i) % MOD

    # invfact[0] is 1. If max_idx_needed is 0, this loop doesn't run for invfact[0].
    # pow(0, MOD-2) is undefined. fact[0] is 1.
    if max_idx_needed >= 0 : # fact[0] always exists
      if fact[max_idx_needed] == 0 and max_idx_needed >= MOD : # Only if MOD is not prime and max_idx_needed >= MOD
           # This case should not happen with prime MOD or max_idx_needed < MOD
           # For MOD = 10^9+7, max_idx_needed = 10^5, fact[max_idx_needed] is non-zero.
           pass # Should handle if fact[max_idx_needed] could be 0
      
      invfact[max_idx_needed] = pow(fact[max_idx_needed], MOD-2, MOD)
      for i in range(max_idx_needed - 1, -1, -1): 
          invfact[i] = (invfact[i+1] * (i+1)) % MOD
    # else case (max_idx_needed < 0) is not possible due to N >= 1.

    def nCr_mod(n, r):
        if r < 0 or r > n:
            return 0
        # n is N-1 or M-1. min N=1, so n can be 0.
        # fact[n], invfact[r], invfact[n-r] must be valid.
        
        num = fact[n]
        den = (invfact[r] * invfact[n-r]) % MOD
        return (num * den) % MOD

    ans = 0

    if M == 0:
        # All N students are Honesty. N announcements of Honesty.
        if N >= K:
            # (N-1)! ways to arrange N distinct people in a circle.
            # fact[0] is 1, so fact[N-1] works for N=1.
            ans = fact[N-1] 
        # else: ans = 0 (already initialized)
    else: # M > 0 (so M >= 1)
          # N >= 1 is given.
        
        # Number of announced H = N + M - 2b >= K
        # 2b <= N + M - K
        # b <= (N + M - K) / 2
        b_limit_from_K = (N + M - K) // 2
        
        # Max b for formula is min(N, M).
        # Also b must be <= b_limit_from_K.
        # b must be >= 1.
        
        upper_b_for_loop = min(N, M) 
        if b_limit_from_K < 1: 
            upper_b_for_loop = 0 # No valid b >= 1 if K is too large
        else:
            upper_b_for_loop = min(upper_b_for_loop, b_limit_from_K)

        current_sum = 0
        for b in range(1, upper_b_for_loop + 1):
            term_comb_N = nCr_mod(N-1, b-1)
            term_comb_M = nCr_mod(M-1, b-1)
            
            # Optimization: if either combination is 0, the term is 0.
            if term_comb_N == 0 or term_comb_M == 0:
                continue
                
            numerator = (fact[N] * fact[M]) % MOD
            inv_b = pow(b, MOD-2, MOD) # b is always >= 1 here.
            
            term = numerator
            term = (term * inv_b) % MOD
            term = (term * term_comb_N) % MOD
            term = (term * term_comb_M) % MOD
            
            current_sum = (current_sum + term) % MOD
        ans = current_sum

    print(ans)

solve()
0