結果

問題 No.117 組み合わせの数
コンテスト
ユーザー yuppe19 😺
提出日時 2015-04-18 23:39:44
言語 Python2
(2.7.18)
結果
AC  
実行時間 1,428 ms / 5,000 ms
コード長 1,255 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 133,380 KB
最終ジャッジ日時 2024-07-04 16:33:25
合計ジャッジ時間 3,891 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
mod = int(1e9) + 7
limit = int(2e6) + 100

def extgcd(x, y):
    u = t = 1
    v = s = 0
    while y > 0:
        q = x / y
        x, y = y, x-q*y
        u, s = s, u-q*s
        v, t = t, v-q*t
    return x, u, v

def get_inv(p, q):
    _, b, _ = extgcd(p, q)
    return b % q

class Combination(object):
    def __init__(self, lim, mod):
        self.lim = lim
        self.mod = mod
        self.f = [1] + [0] * lim
        self.v = [0] * (lim + 1)
        for i in xrange(1, lim):
            self.f[i] = self.f[i-1] * i % mod
        self.v[lim-1] = get_inv(self.f[lim-1], mod)
        for i in xrange(lim-1, 0, -1):
            self.v[i-1] = self.v[i] * i % mod

    nCr = lambda self, n, r: 0 if r < 0 or n < r else self.f[n] * self.v[r] * self.v[n-r] % mod
    nPr = lambda self, n, r: 0 if r < 0 or n < r else self.f[n] * self.v[n-r] % self.mod
    nHr = lambda self, n, r: 1 if n == 0 and r == 0 else 0 if n <= 0 or r < 0 else self.nCr(n+r-1, r)

nya = Combination(limit, mod)
T = int(raw_input())
for _ in xrange(T):
    s = raw_input()
    com = s[0]
    n, r = map(int, s[2:-1].split(','))
    if com == 'C':
        print nya.nCr(n, r)
    elif com == 'P':
        print nya.nPr(n, r)
    else:
        print nya.nHr(n, r)
0