結果

問題 No.117 組み合わせの数
コンテスト
ユーザー yuppe19 😺
提出日時 2020-09-01 12:46:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,656 ms / 5,000 ms
コード長 1,071 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 171,268 KB
最終ジャッジ日時 2024-11-18 12:55:27
合計ジャッジ時間 3,833 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# †
mod = 10**9 + 7

def mod_inv(a, m):
    b, x, y = m, 1, 0
    while b:
        (q, b), a = divmod(a, b), b
        x, y = y, x - y*q
    if a != 1:
        return None
    return x+m if x < 0 else x

###
if __name__ == '__main__':
    N = 2 * 10**6 + 6
    nume = [None] * N
    deno = [None] * N
    nume[0] = 1
    deno[0] = mod_inv(nume[0], mod)
    for i in range(N-1):
        nume[i+1] = nume[i] * (i+1) % mod
        deno[i+1] = mod_inv(nume[i+1], mod)

    def C(n, k):
        if n < k:
            return 0
        return nume[n] * deno[k] * deno[n-k] % mod
    def P(n, k):
        if n < k:
            return 0
        return nume[n] * deno[n-k] % mod
    def H(n, k):
        if (n, k) == (0, 0):
            return 1
        return C(n+k-1, k)

    T = int(input())
    for _ in range(T):
        line = input()
        a, (N, K) = line[0], map(int, line[2:-1].split(','))
        if a == 'C':
            res = C(N, K)
        elif a == 'P':
            res = P(N, K)
        else:
            res = H(N, K)
        print(res)
0