Lucas定理 笔记

Lucas定理

Lucas定理：当 $p$ 是质数时，对于任意正整数 $n,m$ 满足 $\binom{n}{m}\equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n\bmod p}{m\bmod p} \pmod {p}$。

证明：令 $s=\lfloor \frac{n}{p} \rfloor$，$q=n\bmod p$，$t=\lfloor \frac{m}{p} \rfloor$，$r=m \bmod p$。需证明 $\binom{sp+q}{tp+r}\equiv \binom{s}{t}\binom{q}{r} \pmod p$。$(1+x)^n\equiv (1+x)^{sp+q}\equiv((1+x)^p)^s(1+x)^q$。因为 $(1+x)^p=\sum\limits_{i=0}^p \binom{p}{i} x^i$，所以 $(1+x)^p\equiv(1+x^p)$。那么就有 $(1+x)^n\equiv(1+x^p)^s(1+x)^q\equiv\sum\limits_{i=0}^{s} \binom{s}{i} x^{pi}\cdot\sum\limits_{j=0}^q \binom{q}{i}x^i$。考虑 $\binom{n}{m}$ 也就是 $\binom{sp+q}{tp+r}$ 实际上是在多项式 $(1+x)^n$ 中 $x^{tp+r}$ 项的系数，由前面的同余式得到这个系数同时也是 $\binom{s}{t}\binom{q}{r}$ 也就是 $i$ 取 $t$ $j$ 取 $r$ 的情况，所以 $\binom{n}{m}\equiv \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor} \binom{n\bmod p}{m\bmod p} \pmod {p}$ 得证。

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long LL;
#define int LL
const int MAXN = 1e5;
int T;
int fac[MAXN | 1];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline int fast_pow(int x, int y, int p) {
  int res = 1, base = x;
  while (y > 0) {
    if (y & 1) res = (res * base) % p;
    base = base * base % p;
    y >>= 1;
  }
  return res;
}
inline int C(int x, int y, int p) {
  if (x < y) return 0;
  return (fac[x] * fast_pow(fac[x - y], p - 2, p) % p * fast_pow(fac[y], p - 2, p)) % p;
}
int Lucas(int x, int y, int p) {
  if (!y) return 1;
  return C(x % p, y % p, p) * Lucas(x / p, y / p, p) % p;
}
signed main() {
  T = read();
  while (T--) {
    int n = read(), m = read(), p = read();
    fac[0] = 1;
    for (int i = 1; i <= p; ++i) fac[i] = (fac[i - 1] * i) % p;    
    printf("%lld\n", Lucas(n + m, m, p));
  }
  return 0;
}