求组合数

卢卡斯定理（用于解决组合数取模问题【模数必须为质数】）

int qpow(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res*a%p;
        a = a*a%p;
        b >>= 1;
    }
    return res;
}

int C(int a, int b, int p) {
    if (b > a) 
        return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--) {
        res = res*j%p;
        res = res*qpow(i, p-2, p)%p;
    }
    return res;
}

int lucas(int a, int b, int p) {
    if (a<p && b < p)
        return C(a, b, p);
    return C(a%p, b%p, p)*lucas(a/p, b/p, p)%p;
}

signed main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b, p;
        cin >> a >> b >> p;
        //b上a下
        cout << lucas(a, b, p) << "\n";
    }
    return 0;
}

扩展卢卡斯定理（用于解决组合数取模问题【模数可以为任意大于1的整数】）

void exgcd(int a, int b, int &x, int &y) {
    if (!b)
        return (void)(x=1, y=0);
    exgcd(b, a%b, x, y);
    int t = x; x = y;
    y = t-a/b*y;
}

int inv(int a, int p) {
    int x, y;
    exgcd(a, p, x, y);
    return (x+p)%p;
}

int lcm(int a, int b) {
    return a/__gcd(a, b)*b;
}

int qpow(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) 
            res = res*a%p;
        a = a*a%p;
        b >>= 1;
    }
    return res;
}

int F(int n, int p, int pk) {
    if (!n) 
        return 1;
    int rou = 1, rem = 1;
    for  (int i = 1; i <= pk; i++) {
        if (i % p)
            rou = rou*i%p;
    }
    rou = qpow(rou, n/pk, pk);
    for (int i = pk*(n/pk); i <= n; i++) {
        if (i % p)
            rem = rem*(i%pk)%pk;
    }
    return F(n/p, p, pk)*rou%pk*rem%pk; 
}

int G(int n, int p) {
    if (n < p) 
        return 0;
    return G(n/p, p)+(n/p); 
}

int C_PK(int n, int m, int p, int pk) {
    int fz = F(n, p, pk);
    int fm1 = inv(F(m, p, pk), pk);
    int fm2 = inv(F(n-m, p, pk), pk);
    int mi = qpow(p, G(n, p)-G(m, p)-G(n-m, p), pk);
    return fz*fm1%pk*fm2%pk*mi%pk; 
}

int exlucas(int n, int m, int p) {
    int A[1005], B[1005];
    int kkk = p, tot = 0;
    for (int t = 2; t*t <= p; t++) {
        if (!(kkk%t)) {
            int pk = 1;
            while (!(kkk%t)) {
                pk *= t;
                kkk /= t;
            }
            A[++tot] = pk, B[tot] = C_PK(n, m, t, pk);
        }
    }
    if (kkk != 1) {
        A[++tot] = kkk;
        B[tot] = C_PK(n, m, kkk, kkk);
    }
    int ans = 0;
    for (int i = 1; i <= tot; i++) {
        int M = p/A[i], T = inv(M, A[i]);
        ans = (ans+B[i]*M%p*T%p)%p;
    }
    return ans;
}

signed main() {
    int a, b, p;
    cin >> a >> b >> p;
    cout << exlucas(a, b, p) << "\n";
    return 0;
}