博客

//快速幂
LL powermod(LL a,LL n)
{
    if(a==0) return 1;
    LL ret=1,res=a;
    while(n)
    {
        if(n&1) ret=ret*res%mod;
        res=res*res%mod;
        n>>=1;
    }
    return ret;
}
LL fun(LL n,LL m)
{
    if(n>m/2) n=m-n;
    LL  ans=1,i=1;
    while(i<=n)
    {
        ans=ans*(m-i+1)%mod*powermod(i,mod-2)%mod;
        i++;
    }
    return ans;
}
/*
//还可以优化
LL c[1000]={1};
    for(int i=1;i<=n;i++) c[i]=(n-i+1)*powermod(i,mod-2)%mod*c[i-1]%mod;
*/

费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

C(m,n)=m!/(n!*(m-n)!), C(m,n-1)=m!/((n-1)!*(m-n+1)),

所以C(m,n)=(m-n+1)/n*C(m,n-1).

由费马小定理两边除以a,所以1/a=a^(p-2)(mod p).