记录编号 | 401461 | 评测结果 | AAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [HZOI 2015] 组合数取模 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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; }