杨辉三角

void init() {
    for (int i = 0; i < N; i++) {
        c[i][0] = 1; c[i][i] = 1;
        for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
    }
}

线性推阶乘与阶乘逆元

int ifac[N], fac[N];
void init() {
    ifac[0] = ifac[1] = 1; fac[0] = fac[1] = 1;
    for (int i = 2; i < N; i++) {
        ifac[i] = 1LL * (P - P / i) * ifac[P % i] % P;
    }
    for (int i = 2; i < N; i++) {
        ifac[i] = 1LL * ifac[i] * ifac[i - 1] % P;
    }
    for (int i = 2; i < N; i++) {
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
}
int C(int n, int m) {
    if (n < m) return 0;
    return 1LL * fac[n] * ifac[n - m] % P * ifac[m] % P;
}

卢卡斯定理

Lucas

常用于模数为较小的素数：

Lucas(n,m,p)=C(n\bmod p,m\bmod p) * Lucas\left(\frac{n}{p},\frac{m}{p},p\right)

例题：P2480 [SDOI2010]古代猪文

#include <bits/stdc++.h>
using namespace std;
int T;
int n, m, p;

int ksm(int a, int b, int c) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % c) {
        if (b & 1) ret = 1LL * ret * a % c;
    }
    return ret;
}
int ni(int a, int p) {
    return ksm(a, p - 2, p);
}
int C(int n, int m, int p) {
    if (n < m) return 0;
    int ans = 1, tmp = 1;
    for (int i = n, j = n - m + 1; i >= j; i--) ans = 1LL * ans * i % p;
    for (int i = m; i >= 1; i--) tmp = 1LL * tmp * i % p;
    ans = 1LL * ans * ni(tmp, p) % p;
    return ans;
}
int Lucas(int n,int m,int p) {
    if (m == 0) return 1;
    return 1LL * Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &p);
        printf("%d\n", Lucas(n + m, m, p));
    }
    return 0;
}

exLucas

求 C_n^m \pmod p, 1\leq m\leq n\leq 10^{18},2\leq p\leq 1000000 ，不保证 p 是质数。

复杂度：O(P\cdot logP).

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
typedef long long ll;
ll n, m, p;
ll ksm(ll a, ll b, ll p) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) ans = ans * a % p;
    }
    return ans;
}
ll fac(ll n, ll p, ll pk) {
    if (!n) return 1;
    ll ans = 1;
    for (int i = 1; i < pk; i++) if(i % p) ans = ans * i % pk;
    ans = ksm(ans, n / pk, pk);
    for (int i = 1; i <= n % pk; i++) if(i % p) ans = ans * i % pk;
    return ans * fac(n / p, p, pk) % pk;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1; y = 0; return a;
    }
    ll xx, yy, g = exgcd(b, a % b, xx, yy);
    x = yy; y = xx - a / b * yy;
    return g;
}
ll inv(ll a, ll p) {
    ll x = 0, y = 0; exgcd(a, p, x, y);
    return (x % p + p) % p;
}
ll C(const ll n, const ll m, const ll p, const ll pk) {
    if (n < m) return 0;
    ll f1 = fac(n, p, pk), f2 = fac(m, p, pk), f3 = fac(n - m, p, pk);
    ll cnt = 0;
    for (ll i = n; i; i /= p) cnt += i / p;
    for (ll i = m; i; i /= p) cnt -= i / p;
    for (ll i = n - m; i; i /= p) cnt -= i / p;
    return f1 * inv(f2, pk) % pk * inv(f3, pk) % pk * ksm(p, cnt, pk) % pk;
}
ll a[N], c[N];
ll CRT(ll *a, ll *c, int cnt) {
    ll M = 1, ans = 0;
    for (int i = 0; i < cnt; i++) M *= c[i];
    for (int i = 0; i < cnt; i++) {
        ans = (ans + a[i] * (M / c[i]) % M * inv(M / c[i], c[i]) % M) % M;
    }
    return ans;
}
ll exlucas(ll n, ll m, ll p) {
    ll tmp = sqrt(p);
    int cnt = 0;
    for (int i = 2; p > 1 && i <= tmp; i++) {
        ll tmp = 1;
        while (p % i == 0) {p /= i; tmp *= i;}
        if (tmp > 1) {
            a[cnt] = C(n, m, i, tmp);
            c[cnt++] = tmp;
        }
    }
    if (p > 1) {
        a[cnt] = C(n, m, p, p);
        c[cnt++] = p;
    }
    return CRT(a, c, cnt);
}

int main() {
    cin >> n >> m >> p;
    cout << exlucas(n, m, p) << endl;
    return 0;
}