20201116 Day4 卢卡斯定理

Lucas 定理内容如下：对于质数 (p) ，有

[inom{n}{m}mod p = inom{leftlfloor n/p ight floor}{leftlfloor m/p ight floor}cdotinom{nmod p}{mmod p}mod p ]

观察上述表达式，可知 (nmod p) 和 (mmod p) 一定是小于 (p) 的数，可以直接求解， (displaystyleinom{leftlfloor n/p ight floor}{leftlfloor m/p ight floor}) 可以继续用 Lucas 定理求解。这也就要求 (p) 的范围不能够太大，一般在 (10^5) 左右。边界条件：当 (m=0) 的时候，返回 (1) 。

时间复杂度为 (O(f(p) + g(n)log n)) ，其中 (f(n)) 为预处理组合数的复杂度， (g(n)) 为单次求组合数的复杂度。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn=1e5+10;
#define int long long
int n,m,p,T;
int a[maxn];
int pow(int y,int z,int p){
	y%=p;int ans=1;
	for(int i=z;i;i>>=1,y=y*y%p) if(i&1) ans=ans*y%p;
	return ans;	
}
int C(int n,int m){
	if(m>n) return 0;
	return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);	
}
int Lucas(int n,int m){
	if(!m) return 1;
	return C(n%p,m%p)*Lucas(n/p,m/p)%p;	
}
int read(){
	int a=0,op=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') op=-1;c=getchar();}
	while(c>='0'&&c<='9') a*=10,a+=c^48,c=getchar();
	return a*op;	
}
#undef int
int main(){
	#define int long long
	T=read();
	while(T--){
		n=read(),m=read(),p=read();
		a[0]=1;
		for(int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;
		printf("%lld
",Lucas(m+n,n));
	}
    return 0;
}