[docs]
1class ModComb998244353:
2
3 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
4 def __init__(self, limit: int):
5 n = max(1, limit) + 1
6 fact = [0] * n
7 factinv = [0] * n
8 inv = [0] * n
9 fact[0] = 1
10 fact[1] = 1
11 factinv[0] = 1
12 factinv[1] = 1
13 inv[1] = 1
14 for i in range(2, limit + 1):
15 fact[i] = fact[i - 1] * i % 998244353
16 inv[i] = -inv[998244353 % i] * (998244353 // i) % 998244353
17 factinv[i] = factinv[i - 1] * inv[i] % 998244353
18 self._fact = fact
19 self._factinv = factinv
20 self._inv = inv
21 self._limit = limit
22
[docs]
23 def nPr(self, n: int, r: int) -> int:
24 if r < 0 or n < r:
25 return 0
26 return self._fact[n] * self._factinv[n - r] % 998244353
27
[docs]
28 def nCr(self, n: int, r: int) -> int:
29 if r < 0 or n < r:
30 return 0
31 return (
32 (self._fact[n] * self._factinv[r] % 998244353)
33 * self._factinv[n - r]
34 % 998244353
35 )
36
[docs]
37 def nHr(self, n: int, r: int) -> int:
38 return self.nCr(n + r - 1, n - 1)
39
[docs]
40 def nCr2(self, n: int, r: int) -> int:
41 ret = 1
42 if r > n - r:
43 r = n - r
44 for i in range(r):
45 ret *= n - i
46 ret %= 998244353
47 for i in range(1, r + 1):
48 ret *= pow(i, 998244351, 998244353)
49 ret %= 998244353
50 return ret
51
52
[docs]
53class ModComb:
54
55 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
56 def __init__(self, limit: int, mod: int):
57 n = max(1, limit) + 1
58 fact = [0] * n
59 factinv = [0] * n
60 inv = [0] * n
61 fact[0] = 1
62 fact[1] = 1
63 factinv[0] = 1
64 factinv[1] = 1
65 inv[1] = 1
66 for i in range(2, limit + 1):
67 fact[i] = fact[i - 1] * i % mod
68 inv[i] = -inv[mod % i] * (mod // i) % mod
69 factinv[i] = factinv[i - 1] * inv[i] % mod
70 self._fact = fact
71 self._factinv = factinv
72 self._inv = inv
73 self._limit = limit
74 self._mod = mod
75
[docs]
76 def nPr(self, n: int, r: int) -> int:
77 if r < 0 or n < r:
78 return 0
79 return self._fact[n] * self._factinv[n - r] % self._mod
80
[docs]
81 def nCr(self, n: int, r: int) -> int:
82 if r < 0 or n < r:
83 return 0
84 return (
85 (self._fact[n] * self._factinv[r] % self._mod)
86 * self._factinv[n - r]
87 % self._mod
88 )
89
[docs]
90 def nHr(self, n: int, r: int) -> int:
91 return self.nCr(n + r - 1, n - 1)
92
[docs]
93 def nCr2(self, n: int, r: int) -> int:
94 ret = 1
95 if r > n - r:
96 r = n - r
97 for i in range(r):
98 ret *= n - i
99 ret %= self._mod
100 for i in range(1, r + 1):
101 ret *= pow(i, self._mod - 2, self._mod)
102 ret %= self._mod
103 return ret
104
105
[docs]
106class ModComb1000000007:
107
108 # nCr2のみをつかうときなどは、limit=-1とかにすると吉
109 def __init__(self, limit: int):
110 n = max(1, limit) + 1
111 fact = [0] * n
112 factinv = [0] * n
113 inv = [0] * n
114 fact[0] = 1
115 fact[1] = 1
116 factinv[0] = 1
117 factinv[1] = 1
118 inv[1] = 1
119 for i in range(2, limit + 1):
120 fact[i] = fact[i - 1] * i % 1000000007
121 inv[i] = -inv[1000000007 % i] * (1000000007 // i) % 1000000007
122 factinv[i] = factinv[i - 1] * inv[i] % 1000000007
123 self._fact = fact
124 self._factinv = factinv
125 self._inv = inv
126 self._limit = limit
127
[docs]
128 def nPr(self, n: int, r: int) -> int:
129 if r < 0 or n < r:
130 return 0
131 return self._fact[n] * self._factinv[n - r] % 1000000007
132
[docs]
133 def nCr(self, n: int, r: int) -> int:
134 if r < 0 or n < r:
135 return 0
136 return (
137 (self._fact[n] * self._factinv[r] % 1000000007)
138 * self._factinv[n - r]
139 % 1000000007
140 )
141
[docs]
142 def nHr(self, n: int, r: int) -> int:
143 return self.nCr(n + r - 1, n - 1)
144
[docs]
145 def nCr2(self, n: int, r: int) -> int:
146 ret = 1
147 if r > n - r:
148 r = n - r
149 for i in range(r):
150 ret *= n - i
151 ret %= 1000000007
152 for i in range(1, r + 1):
153 ret *= pow(i, 1000000005, 1000000007)
154 ret %= 1000000007
155 return ret