結果

問題 No.117 組み合わせの数
コンテスト
ユーザー h173309
提出日時 2020-05-06 09:21:04
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,344 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-06-28 03:24:29
合計ジャッジ時間 800 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Factorial():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = [1]
        self._size = 1
    
    def __call__(self, n):
        '''n! % mod '''
        if n >= self.mod:
            return 0
        make(n)
        return self._factorial[n]
    
    def make(self, n):
        if n >= self.mod:
            n = self.mod
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._factorial.append(self._factorial[-1]*i % self.mod)
        self._size = n+1

class Modinv():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._modinv = [1]
        self._size = 1
    
    def __call__(self, n):
        '''n^-1 % mod '''
        n %= mod
        make(n)
        return self._modinv[n]
    
    def make(self, n):
        if self._size < n+1:
            for i in range(self._size, n+1):
                self._modinv.append(self.inverse(i))
        self._size = n+1
    
    @staticmethod
    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 inverse(self, a):
        g, x, y = xgcd(a, self.mod)
        assert g == 1, 'modular inverse does not exist'
        return x % mod

class Combination():
    def __init__(self, mod=10**9 + 7):
        self.mod = mod
        self._factorial = Factorial(mod)
        self._modinv = Modinv(mod)
    
    def __call__(self, n, r):
        ''' nCr % mod '''
        if not 0 <= r <= n:
            return 0
        a, b, c = map(self.factorial, (n, r, n-r))
        return a*self._modinv(b*c % mod) % mod
    
    def comb_with_repetition(self, n, r):
        ''' nHr % mod '''
        return self.__call__(n+r-1, r)
    
    def perm(self, n, r):
        ''' nPr % mod '''
        if not 0 <= r <= n:
            return 0
        a, b = map(self.factorial, (n, n-r))
        return a*self._modinv(b) % mod
comb = Combination()
perm = comb.perm
comb_with_repetition = comb.comb_with_repetition

from re import split
for _ in range(int(input())):
    q, n, r, *_ = split('[(,)]', input())
    if q == 'C':
        print(comb(n, r))
    elif q == 'P':
        print(perm(n, r))
    else:
        print(comb_with_repetition(n, r))
0