結果

問題 No.117 組み合わせの数
ユーザー h173309h173309
提出日時 2019-10-06 20:48:19
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,933 bytes
コンパイル時間 166 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 57,048 KB
最終ジャッジ日時 2024-10-11 01:41:27
合計ジャッジ時間 1,480 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
inputs = sys.stdin.readlines()

def is_prime(n):
    assert n >= 1,  'Argument Error! n is "1 <= n".'
    for i in range(2, n + 1):
        if i ** 2 > n:
            break
        if n % i == 0:
            return False
    return n != 1

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, mod):
    g, x, y = xgcd(a, mod)
    assert g == 1, 'modular inverse does not exist'
    return x % mod

factorials = [1]
def factorial(n, mod):
    # n! % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    if len(factorials) < n+1:
        for i in range(len(factorials), n+1):
            factorials.append(factorials[-1]*i % mod)
    return factorials[n]

def comb(n, r, mod):
    # nCr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    assert n >= r >= 0, 'Argument Error! r is "0 <= r <= n".'
    
    return perm(n, r, mod) * modinv(factorial(r, mod), mod) % mod

def comb_with_repetition(n, r, mod):
    # nHr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    assert n+r-1 >= r >= 0, 'Argument Error! r is "0 <= r <= n+r-1".'
    
    return comb(n+r-1, r, mod)

def perm(n, r, mod):
    # nPr % mod
    assert n >= 0, 'Argument Error! n is "0 <= n".'
    return factorial(n, mod) * modinv(factorial(n-r, mod), mod) % mod
    assert n >= r >= 0, 'Argument Error! r is "0 <= r <= n".'

N = int(inputs[0])
data = [x.translate(str.maketrans({'(': ',', ')': ''})).split(',') for x in inputs[1:N+1]]
data = [(x[0], int(x[1]), int(x[2])) for x in data]

MOD = 10 ** 9 + 7

for x, y in zip(data, ans):
    try:
        if x[0] == 'C':
                print(comb(x[1], x[2], MOD))
        elif x[0] == 'P':
            print(perm(x[1], x[2], MOD))
        else:
            print(comb_with_repetition(x[1], x[2], MOD))
    except:
        print(0)
0