记录编号	401461	评测结果	AAAAAAAAAAA
题目名称	[HZOI 2015] 组合数取模	最终得分	100
用户昵称	yourfather	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-05-02 19:19:33	内存使用	0.31 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int SIZEN = 200010;
#define int long long
LL P,N,M;
inline int qpow(int x,int len,int P){
	int ret = 1;
	for(;len;len>>=1,x = 1LL*x*x%P){
		if(len & 1)ret = 1LL*ret * x%P;
	}
	return ret;
}
int Fact(int n,int p,int t){
	if(!n)return 1;
	int ret = 1,mod = qpow(p,t,P+1);
	if(n >= mod)for(int i = 1;i <= mod;i++)if(i % p)ret = (LL)ret*i%mod;
	ret = qpow(ret,n/mod,mod);
	for(int i = n/mod*mod+1;i <= n;i++)if(i % p)ret = (LL)ret*i%mod;//printf("ret = %lld\n",ret);
	return ret*Fact(n/p,p,t)%mod;
}
void Extend_gcd(int a,int b,int &x,int &y){
	if(b == 0){x = 1;y = 0;return;}
	Extend_gcd(b,a%b,x,y);
	int tmp = x;x = y;y = tmp-(a/b)*y;
}
int reverse(int x,int p){
	int inv,tmp;
	Extend_gcd(x,p,inv,tmp);
	return (inv % p+p)%p;
}
int C(int n,int m,int p,int t){
	int mod = qpow(p,t,P+1);
	int a,b,c,ap(0),bp(0),cp(0),total(0);
	for(int i = n;i;i/=p)ap += i/p;
	for(int i = m;i;i/=p)bp += i/p;
	for(int i = n-m;i;i/=p)cp += i/p;
	total = qpow(p,ap-bp-cp,mod);
	a = Fact(n,p,t);
	b = Fact(m,p,t);
	c = Fact(n-m,p,t);//printf("a = %lld,b = %lld,c = %lld,n = %lld,m = %lld,mod = %lld\n",a,b,c,n,m,mod);
	return total * a%mod*reverse(b,mod)%mod*reverse(c,mod)%mod;
}
int CRT(int *p,int *a,int M,int n){
	int ret = 0;
	for(int i = 1;i <= n;i++){
		int m = M/p[i];
		ret += (LL)m*reverse(m,p[i])%M*a[i]%M;
		ret %= M;
	}
	if(ret < 0)ret+=M;
	return ret;
}

int Lucas(int n,int m,int mod){
	int A[210]={0},P[210]={0},cntt=0,x = mod;
	for(int i = 2;i*i <= mod;i++)if(mod % i == 0){
		int t = 0;
		while(mod % i == 0){
			t++;mod /= i;
		}
		P[++cntt] = qpow(i,t,x+1);
		A[  cntt] = C(n,m,i,t);
	}
	if(mod > 1){P[++cntt] = mod;A[cntt] = C(n,m,mod,1);}
	//for(int i = 1;i <= cnt;i++)printf("P[%lld] = %lld,A[%lld] = %lld\n",i,P[i],i,A[i]);
	return CRT(P,A,x,cntt);
}
int query(int x,int y,LL z){
	if(x % 2 == 0)x++;
	if(y % 2 == 0)y--,z--;
	int be,ed;
	be = (x+1)/2;ed = (y-1)/2;//printf("ed-be+1 = %lld z = %lld\n",ed-be+1,z);
	if(!y||!x||x > N||y > N||ed - be + 1 <= 0||ed-be+1<z||z < 0)return 0;
	return Lucas(ed-be+1,z,P);
}
signed main(){
	freopen("combinatorial_mod.in","r",stdin);
	freopen("combinatorial_mod.out","w",stdout);
	scanf("%lld%lld%lld",&N,&M,&P);
	printf("%lld\n",Lucas(N,M,P));
	return 0;
}