傳送門：

P3807 【模板】盧卡斯定理/Lucas 定理 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)https://www.luogu.com.cn/problem/P3807題干：

給定整數n,m,p?的值，求出C（n+m，n）?mod p?的值。

輸入數據保證?p?為質數。

注:?C?表示組合數。

輸入格式

本題有多組數據。

第一行一個整數?T，表示數據組數。

對于每組數據:

一行，三個整數?n,m,p。

輸出格式

對于每組數據，輸出一行，一個整數，表示所求的值。

輸入輸出樣例

輸入 #1復制

2
1 2 5
2 1 5

輸出 #1復制

3
3

說明/提示

對于 100%?的數據1≤n,m,p≤10^5，1≤T≤10。

?Lucas 定理：

相當于：

?

這是一道板子題，由組合數的公式：

我們不難發現 只要求出 遞推n！模上p的值，就能得到 m！，（n-m）！。

然后因為m！，（n-m）！在分母，所以我們只需要求出 逆元即可。

由于模數p是質數，所以用到費馬小定理求解。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;typedef long long ll;
const ll N = 1e5+7;
const ll M = 1e6+7;
ll fac[N],C[N];
ll get_inv(ll a,ll b,ll p) {ll s = 1;while (b) {if (b & 1)s = s * a % p;a = a * a % p;b >>= 1;}return s;
}
ll get_C(ll n, ll m,ll P) {if (m > n)return 0;return (fac[n] * get_inv(fac[m],P-2,P) % P) * get_inv(fac[n - m],P-2,P) % P;
}
ll Lucas(ll n,ll m,ll P) {if (m == 0)return 1;return get_C(n % P, m % P,P) * Lucas(n / P, m / P,P)%P;
}int main() {int t;cin >> t;while (t--) {ll n, m,p;cin >> n >> m >> p;fac[0] = 1;for (ll i = 1; i <= n+m; i++) {fac[i] = fac[i - 1] * i % p;}cout << Lucas(n+m, n, p)<<endl;}
}