[Luogu 3807]【模板】卢卡斯定理

Description

给定n,m,p( $1≤n,m,p≤10^5)$

求 $C_{n+m}^{m} mod p$

保证P为prime

C表示组合数。

一个测试点内包含多组数据。

Input

第一行一个整数T(

第二行开始共T行，每行三个数n m p，意义如上

Output

共T行，每行一个整数表示答案。

Sample Input

2
1 2 5
2 1 5

Sample Output

3
3

题解

$Lucas$定理。

就是$C^m _n mod p = C^{m/p} _{n/p}*C^{m mod p} _{n mod p} mod p$。

证明：不会。记着就行。

代码实现方面，注意两点：

1.对于$C^{m/p} _{n/p}$部分可以继续使用$Lucas$定理递归求解。

2.求逆元，可以用费马小定理做快速幂，当然也可以线性预处理阶乘逆元。注意，若线性预处理，需要将$0$位赋为$1$（很好理解，不做解释）。

 1 //It is made by Awson on 2017.10.7
 2 #include <map>
 3 #include <set>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <cstdio>
10 #include <string>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 using namespace std;
19 const int N = 1e5;
20 
21 int n, m, p;
22 int A[N+5], B[N+5];
23 
24 int C(int n, int m, int p) {
25     if (m > n) return 0;
26     return (LL)A[n]*B[n-m]%p*B[m]%p;
27 }
28 int Lucas(int n, int m, int p) {
29     if (!m) return 1;
30     return (LL)C(n%p, m%p, p)*Lucas(n/p, m/p, p)%p;
31 }
32 void work() {
33     scanf("%d%d%d", &n, &m, &p);
34     A[0] = B[0] = A[1] = B[1] = 1;
35     n += m;
36     for (int i = 2; i <= p; i++)
37         B[i] = -(LL)(p/i)*B[p%i]%p;
38     for (int i = 2; i <= p; i++)
39         A[i] = (LL)A[i-1]*i%p,
40         B[i] = (LL)B[i-1]*B[i]%p;
41     printf("%d
", (Lucas(n, m, p)+p)%p);
42 }
43 int main() {
44     int t;
45     scanf("%d", &t);
46     while (t--)
47         work();
48     return 0;
49 }