結果
問題 | No.117 組み合わせの数 |
ユーザー |
|
提出日時 | 2023-04-23 01:42:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 667 ms / 5,000 ms |
コード長 | 2,630 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 243,968 KB |
最終ジャッジ日時 | 2024-11-07 12:02:43 |
合計ジャッジ時間 | 2,190 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
from typing import Listclass Binominal:def __init__(self, mod: int, max: int=0) -> None:self.mod = modself.f = f = [1]self.g = [1]self.h = [1]while max >= len(f): self.extend()def extend(self) -> None:mod = self.modf, g, h = self.f, self.g, self.hn = len(f)m = n << 1f[n:] = [0] * ng[n:] = [0] * nh[n:] = [0] * nfor i in range(n, m): f[i] = f[i - 1] * i % modg[-1] = pow(f[-1], mod - 2, mod)h[-1] = g[-1] * f[-2] % modfor i in range(m - 2, n - 1, -1):g[i] = g[i + 1] * (i + 1) % modh[i] = g[i] * f[i - 1] % moddef fac(self, i: int) -> int:if i < 0: return 0f = self.f; extend = self.extendwhile i >= len(f): extend()return f[i]def finv(self, i: int) -> int:if i < 0: return 0g = self.g; extend = self.extendwhile i >= len(g): extend()return g[i]def inv(self, i: int) -> int:if i < 0:tmp = pow(-i, self.mod - 2, self.mod)if tmp: return self.mod - tmpelse: return 0h = self.h; extend = self.extendwhile i > len(h): extend()return h[i]def __call__(self, n: int, r: int) -> int:return self.C(n, r)def multinominal(self, r: List[int]) -> int:n = 0for x in r:if x < 0: return 0n += xres = self.fac(n)mod = self.mod; finv = self.finvfor x in r: res = res * finv(x) % modreturn resdef C_naive(self, n: int, r: int) -> int:if n < 0 or n < r or r < 0: return 0mod = self.modres = 1r = min(r, n - r)for i in range(1, r + 1):res = (res * pow(i, mod - 2, mod) % mod) * nn -= 1return resdef C(self, n: int, r: int) -> int:if n < 0 or n < r or r < 0: return 0return (self.fac(n) * self.finv(n - r) % self.mod) * self.finv(r) % self.moddef P(self, n: int, r: int) -> int:if n < 0 or n < r or r < 0: return 0return self.fac(n) * self.finv(n - r) % self.moddef H(self, n: int, r: int) -> int:if n < 0 or r < 0: return 0return self.C(n + r - 1, r) if r else 1T = int(input())binominal = Binominal(1_000_000_007)for _ in range(T):S = input()n, r = map(int,S[2:-1].split(','))if S[0] == "C":print(binominal.C(n, r))elif S[0] == "P":print(binominal.P(n, r))else:print(binominal.H(n, r))