花了半天时间，总算把这个算法搞懂了

代码 1：直接算C[a,b]

组合数 II 之所以不直接算 C[a,b]，是因为它的询问有 $n^5$ 次，不先预处理会超时，但这里 n 只有 20次，所以在用 lucas 定理时再求具体某个C[a,b]也是可以的

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 7;

int p;

LL fact[N], infact[N];

LL qmi(int a, int k, int p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 直接算法c[a][b]
LL c(int a, int b) {
    int res = 1;
    for (int i = a; i > a - b; i -- ) res = (LL)res * i % p; // 包含了 a < b的情况

    for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, p - 2, p) % p;
    return res;
}

LL lucas(LL a, LL b) {

    if (a < p && b < p) return c(a, b);

    return c(a % p, b % p) * lucas(a / p, b / p) % p; 
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        LL a, b;
        cin >> a >> b >> p;

        cout << lucas(a, b) << endl;
    }

    return 0;
}

代码 2：先预处理 $1e5$个阶乘，然后再用 lucas 定理

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 7;

int p;

LL fact[N], infact[N];

LL qmi(int a, int k, int p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘
void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < p; i++) { // p设为全局变量，想一想算多少i才够
        fact[i] = fact[i - 1] * i % p;
        infact[i] = infact[i - 1] * qmi(i, p - 2, p) % p;
    }
}

LL lucas(LL a, LL b) {
    if (a < b) return 0;
    if (a < p && b < p) return fact[a] * infact[a - b] % p * infact[b] % p;

    LL x = a % p, y = b % p;
    if (x < y) return 0;
    LL tmp = fact[x] * infact[x - y] % p * infact[y] % p;
    return tmp * lucas(a / p, b / p) % p; 
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        LL a, b;
        cin >> a >> b >> p;

        init(); // 先预处理阶乘
        cout << lucas(a, b) << endl;
    }

    return 0;
}