結果

問題 No.117 組み合わせの数
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-07-27 13:06:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,566 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 109,952 KB
最終ジャッジ日時 2024-11-06 17:55:36
合計ジャッジ時間 2,044 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#!/usr/bin/env pypy3

import re


# 参考 #107170
class ModPrime(object):

    def __init__(self, p=10**9+7, limit=10**8):
        self.fact = [1 for _ in range(limit + 1)]
        self.fact_inv = [1 for _ in range(limit + 1)]
        self.p = p
        self.current_limit = None
        self.pre_calc(limit)

    def pre_calc(self, limit):
        p = self.p
        for i in range(1, limit + 1):
            self.fact[i] = i * self.fact[i - 1] % p
        self.fact_inv[limit] = pow(self.fact[limit], p - 2, p)
        for i in range(1, limit + 1)[::-1]:
            self.fact_inv[i - 1] = self.fact_inv[i] * i % p
        self.current_limit = limit

    def perm(self, n, k):
        return 0 if n < k else self.fact[n] * self.fact_inv[n - k] % self.p

    def combi(self, n, k):
        return self.perm(n, k) * self.fact_inv[k] % self.p

    def multi_combi(self, n, k):
        return 1 if n == k == 1 else self.combi(n + k - 1, k)


def main():
    p = 10 ** 9 + 7
    limit = 2 * 10 ** 6 + 10
    mp = ModPrime(p, limit)
    ptn = re.compile(r"(?P<func>[CPH])\((?P<n>[0-9]+),(?P<k>[0-9]+)\)")
    t = int(input())
    for _ in range(t):
        mobj = re.match(ptn, input())
        assert mobj is not None
        f = mobj.group("func")
        n = int(mobj.group("n"))
        k = int(mobj.group("k"))
        if f == "C":
            print(mp.combi(n, k))
        elif f == "P":
            print(mp.perm(n, k))
        elif f == "H":
            print(mp.multi_combi(n, k))
        else:
            assert False


if __name__ == '__main__':
    main()
0