-
Notifications
You must be signed in to change notification settings - Fork 0
/
modulo.cc
45 lines (42 loc) · 942 Bytes
/
modulo.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int modpow(long long a, long long n, int mod) {
/* O(log n) */
assert(a>=0 && n >= 0);
a %= mod;
long long r = 1;
while (n > 0) {
if (n & 1) r = r * a % mod;
a = a * a % mod;
n >>= 1;
}
return (int)r;
}
int modinv(long long a, int mod) {
/* O(log mod) */
assert(a>=0);
#ifdef _GLIBCXX_ASSERTIONS
assert(gcd(a,mod)==1);
#endif
long long b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= mod;
if (u < 0) u += mod;
return (int)u;
}
int choose(long long n, int k, int mod) {
/* O(k log mod) */
assert(n>=0 && k>=0 && k < mod);
long long c = 1;
for(int i=1; i<=k; i++) c = (n-i+1) % mod * c % mod * modinv(i, mod) % mod;
return (int)c;
}
int permutation(long long n, int k, int mod) {
/* O(k) */
assert(n>=0 && k>=0);
long long c = 1;
for(long long i=n; i>n-k; --i) c = i % mod * c % mod;
return (int)c;
}