P3807 【模板】卢卡斯定理/Lucas 定理

C⁡nmmod⁡p=C⁡n/pm/p×C⁡nmod⁡pmmod⁡pmod⁡p\operatorname{C}^m_n\operatorname{mod}p=\operatorname{C}^{m/p}_{n/p}\times \operatorname{C}^{m\operatorname{mod}p}_{n \operatorname{mod}p}\operatorname{mod}p

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#define re register
typedef long long ll;
const int MAXC = 1e5 + 1e5;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1; y = 0;
        return a;
    } else {
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}
int inv(int x, int p) {
    int ans, k;
    exgcd(x, p, ans, k);
    return (ans % p + p) % p;
}

int fac[MAXC + 10];
void EvaFac(int top, int p) {
    fac[0] = 1;
    for (re int i = 1; i <= top; ++i) {
        fac[i] = ((ll)fac[i - 1] * i) % p;
    }
}

int C(int n, int m, int p) {
    if (n < m) return 0;
    return (ll)fac[n] * inv(fac[m], p) % p * inv(fac[n - m], p) % p;
}

int Lucas(int n, int m, int p) {
    if (!m) return 1;
    return (ll)Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

int T, n, m, p;
int main() {
    read(T);
    while (T--) {
        read(n), read(m), read(p);
        EvaFac(MAXC, p);
        n += m;
        m = n - m;
        printf("%d\n", Lucas(n, m, p));
    }
}