【Lucas定理】组合数取模算法

Step1 Problem:

原题组合数在取模下的算法，用作模板保存。

Step2 Ideas:

学习链接学习链接1

Step3 code：

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<bitset>
 7 #include<cassert>
 8 #include<cctype>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<ctime>
12 #include<deque>
13 #include<iomanip>
14 #include<list>
15 #include<map>
16 #include<queue>
17 #include<set>
18 #include<stack>
19 #include<vector>
20 #define lt k<<1
21 #define rt k<<1|1
22 #define lowbit(x) x&(-x)
23 #define lson l,mid,lt
24 #define rson mid+1,r,rt
25 using namespace std;
26 typedef long long  ll;
27 typedef long double ld;
28 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
29 #define mem(a, b) memset(a, b, sizeof(a))
30 //#define int ll
31 const double pi = acos(-1.0);
32 const double eps = 1e-6;
33 const ll mod = 1e9 + 7;
34 const int inf = 0x3f3f3f3f;
35 const ll INF = 0x3f3f3f3f3f3f3f3f;
36 const int maxn = 2e5 + 5;
37 int T, n, m, p;
38 ll a[maxn], b[maxn];
39 ll lucas(int x, int y)
40 {
41     if (x < y) return 0;
42     else if (x < p) return b[x] * a[y] * a[x - y] % p;
43     else return lucas(x / p, y / p) * lucas(x % p, y % p) % p;
44 }
45 int main()
46 {
47 #ifdef ONLINE_JUDGE
48 #else 
49     freopen("input.txt", "r", stdin);
50 #endif
51     cin >> T;
52     while (T--)
53     {
54         cin >> n >> m >> p;
55         a[0] = a[1] = b[0] = b[1] = 1;
56         for (int i = 2; i <= n + m; i++) b[i] = b[i - 1] * i % p;//求阶乘
57         for (int i = 2; i <= n + m; i++) a[i] = (p - p / i) * a[p % i] % p;//求逆元
58         for (int i = 2; i <= n + m; i++) a[i] = a[i - 1] * a[i] % p;
59         cout << lucas(n + m, m) << endl;
60     }
61 
62     return 0;
63 }

【Lucas定理】组合数取模算法

Step1 Problem:

Step2 Ideas:

Step3 code：