結果
問題 | No.502 階乗を計算するだけ |
ユーザー | hinamimi |
提出日時 | 2020-07-24 18:27:23 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,808 bytes |
コンパイル時間 | 687 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 575,752 KB |
最終ジャッジ日時 | 2023-09-07 22:16:39 |
合計ジャッジ時間 | 7,159 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,328 KB |
testcase_01 | AC | 75 ms
71,496 KB |
testcase_02 | AC | 75 ms
71,576 KB |
testcase_03 | AC | 76 ms
71,332 KB |
testcase_04 | AC | 77 ms
71,560 KB |
testcase_05 | AC | 76 ms
71,104 KB |
testcase_06 | AC | 76 ms
71,312 KB |
testcase_07 | AC | 77 ms
71,352 KB |
testcase_08 | AC | 76 ms
71,108 KB |
testcase_09 | AC | 75 ms
71,104 KB |
testcase_10 | AC | 76 ms
71,308 KB |
testcase_11 | AC | 76 ms
71,324 KB |
testcase_12 | AC | 75 ms
71,100 KB |
testcase_13 | AC | 75 ms
71,376 KB |
testcase_14 | AC | 74 ms
71,356 KB |
testcase_15 | AC | 74 ms
71,304 KB |
testcase_16 | AC | 76 ms
71,404 KB |
testcase_17 | AC | 75 ms
71,260 KB |
testcase_18 | AC | 74 ms
71,360 KB |
testcase_19 | AC | 75 ms
71,504 KB |
testcase_20 | AC | 76 ms
71,104 KB |
testcase_21 | AC | 76 ms
71,304 KB |
testcase_22 | AC | 136 ms
143,604 KB |
testcase_23 | AC | 95 ms
93,436 KB |
testcase_24 | AC | 118 ms
122,740 KB |
testcase_25 | AC | 86 ms
80,300 KB |
testcase_26 | AC | 101 ms
101,376 KB |
testcase_27 | AC | 92 ms
89,552 KB |
testcase_28 | AC | 98 ms
95,820 KB |
testcase_29 | AC | 85 ms
84,120 KB |
testcase_30 | AC | 127 ms
136,180 KB |
testcase_31 | AC | 106 ms
104,992 KB |
testcase_32 | MLE | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
ソースコード
class Factorial(): def __init__(self, mod=10**9 + 7): self.m = mod self._factorial = [1] self._size = 1 self._factorial_inv = [1] self._size_inv = 1 def __call__(self, n): return self.fact(n) def fact(self, n): """ n! (mod m) """ if n >= self.m: return 0 self._make(n) return self._factorial[n] def _make(self, n): """ Calc from self._size to n!^-1 : O(n) """ if n >= self.m: n = self.m if self._size < n+1: for i in range(self._size, n+1): self._factorial.append(self._factorial[i-1]*i % self.m) self._size = n+1 def fact_inv(self, n): """ n!^-1 (mod m) """ if n >= self.m: raise ValueError('Modinv is not exist! arg={}'.format(n)) if self._size_inv < n+1: self._factorial_inv += [-1] * (n+1-self._size_inv) self._size_inv = n+1 if self._factorial_inv[n] == -1: self._factorial_inv[n] = self.modinv(self.fact(n)) return self._factorial_inv[n] def _make_inv(self, n, r=1): """ Calc r!^1 ... n!^-1 : O(n-r) """ if n >= self.m: n = self.m - 1 if self._size_inv < n+1: self._factorial_inv += [-1] * (n+1-self._size_inv) self._size_inv = n+1 self._factorial_inv[n] = self.modinv(self.fact(n)) for i in range(n, r+1, -1): self._factorial_inv[i-1] = self._factorial_inv[i]*i % self.m @staticmethod def xgcd(a, b): """ Return (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b) """ x0, x1, y0, y1 = 0, 1, 1, 0 while a != 0: (q, a), b = divmod(b, a), a y0, y1 = y1, y0 - q * y1 x0, x1 = x1, x0 - q * x1 return b, x0, y0 def modinv(self, n): """ n^-1 (mod m) """ g, x, _ = self.xgcd(n, self.m) if g != 1: raise ValueError('Modinv is not exist! arg={}'.format(n)) return x % self.m def comb(self, n, r): """ nCr (mod m) """ if r > n: return 0 t = self(n)*self.fact_inv(n-r) % self.m return t*self.fact_inv(r) % self.m def comb_(self, n, r): """ nCr (mod m) : O(r) """ c = 1 for i in range(1, r+1): c *= (n-i+1) * self.fact_inv(i) c %= self.m return c def comb_with_repetition(self, n, r): """ nHr (mod m) """ t = self(n+r-1)*self.fact_inv(n-1) % self.m return t*self.fact_inv(r) % self.m def perm(self, n, r): """ nPr (mod m) """ if r > n: return 0 return self(n)*self.fact_inv(n-r) % self.m print(Factorial()(int(input())))