组合数(1e5）

发表于 分类于 ， 阅读次数： 本文字数： 569 阅读时长 ≈ 1 分钟 
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
i64 fpow(i64 a, i64 x) {
  i64 res = 1;
  while (x) {
    if (x & 1)
      res = res * a % mod;
    a = a * a % mod;
    x >>= 1;
  }
  return res % mod;
}

const i64 M = 1e5;
i64 fac[M + 10], fnv[M + 10];

void init() {
  fac[0] = 1;
  for (int i = 1; i <= M; i++)
    fac[i] = fac[i - 1] * i % mod;
  fnv[M] = fpow(fac[M], mod - 2);
  for (int i = M; i >= 1; i--)
    fnv[i - 1] = fnv[i] * i % mod;
  // assert(fnv[1] == 1);
}

i64 C(i64 n, i64 m) {
  if (m < 0 || m > n)
    return 0;
  return fac[n] * fnv[m] % mod * fnv[n - m] % mod;
} // c(n,m)
i64 A(i64 n, i64 m) {
  if (m < 0 || m > n)
    return 0;
  return fac[n] * fnv[m] % mod;
} // a(n,m);