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

题面

给定整数 \(n, m, p\) 的值，求出 \(C_{n + m}^n \bmod p\) 的值。

输入数据保证 \(p\) 为质数。

注: \(C\) 表示组合数。

对于 \(100\%\) 的数据，\(1 \leq n, m, p \leq 10^5\)。

思路

Lucas定理模版题。数字大的用Lucas分解，数字小的直接算。

C(n,m) mod p=C(n%p,m%p) * C(n/p,m/p) mod p

除法用逆元。

代码

#include 
#define int long long
using namespace std;

int fact[100005];
int data[1000005];
int n,m,p;

int lucas(int a,int b){
	if(a>n>>m>>p;
	n+=m;
	data[0]=data[1]=fact[0]=fact[1]=1;
	for(int i=2;i<=n;i++){
		fact[i]=fact[i-1]*i%p;
		data[i]=(p-p/i)*data[p%i]%p;
	}
	for(int i=2;i<=n;i++){ // 无法理解的代码开始了
		data[i]=data[i-1]*data[i]%p;
	}
	return lucas(n,m);
}

signed main(){
	int t;
	cin>>t;
	while(t--){
		cout<