http://codeforces.com/gym/100633/problem/J
Lucas定理P不是质数裸题
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; inline ll read(){ char c=getchar();ll x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll n,m,MOD; ll Pow(ll a,ll b,ll P){ ll ans=1; for(;b;b>>=1,a=a*a%P) if(b&1) ans=ans*a%P; return ans; } void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ if(b==0) d=a,x=1,y=0; else exgcd(b,a%b,d,y,x),y-=(a/b)*x; } ll Inv(ll a,ll n){ ll d,x,y; exgcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } ll Fac(ll n,ll p,ll pr){ if(n==0) return 1; ll re=1; for(ll i=2;i<=pr;i++) if(i%p) re=re*i%pr; re=Pow(re,n/pr,pr); ll r=n%pr; for(int i=2;i<=r;i++) if(i%p) re=re*i%pr; return re*Fac(n/p,p,pr)%pr; } ll C(ll n,ll m,ll p,ll pr){ if(n<m) return 0; ll x=Fac(n,p,pr),y=Fac(m,p,pr),z=Fac(n-m,p,pr); ll c=0; for(ll i=n;i;i/=p) c+=i/p; for(ll i=m;i;i/=p) c-=i/p; for(ll i=n-m;i;i/=p) c-=i/p; ll a=x*Inv(y,pr)%pr*Inv(z,pr)%pr*Pow(p,c,pr)%pr; return a*(MOD/pr)%MOD*Inv(MOD/pr,pr)%MOD; } ll Lucas(ll n,ll m){ ll x=MOD,re=0; for(ll i=2;i<=MOD;i++) if(x%i==0){ ll pr=1; while(x%i==0) x/=i,pr*=i; re=(re+C(n,m,i,pr))%MOD; } return re; } int main(){ //freopen("in","r",stdin); n=read();m=read();MOD=read(); printf("%I64d",Lucas(n,m)); }