组合数，计算上的优化

逆元的主要用处，当求a/b模p时，a与b过大，就可以用逆元，求出b的逆元，一般是pow(b,p-2),a/b及等于a*b逆。

组合数使用了这一个特性，求出阶乘的逆

 1 int fac[N]//表示阶乘;
 2 int infac[N]//表示阶乘的逆;
 3 int main(){
 4     int a,b;
 5     fac[0]=infac[0]=1;
 6     for(int i=1;i<N;++i){
 7         fac[i]=1ll*fac[i-1]*i%mod;
 8         infac[i]=1ll*infac[i-1]*qmi(i,mod-2,mod)%mod;
 9     }
10     cin>>a>>b;
11     cout<<1ll*fac[a]*infac[a-b]%mod*infac[b]%mod<<endl;
12     return 0;
13 }

两大数相乘在取模和容易爆

 1 ll um(ll x,ll y,ll mod){
 2     x%=mod;
 3     y%=mod;
 4     ll d=((long double)x*y/mod);
 5     d=x*y-d*mod;
 6     if(d>=mod){
 7         d%=mod;
 8     }
 9     if(d<0){
10         d+=mod;
11     }
12     return d;
13 }

快速乘与快速幂类似，原理是转化成相加

int qmi(int x,int y,int mod){
    int res=0;
    while(y){
        if(y&1){
            res=（res+x）%mod;
        }
        x=（x+x）%mod;
        y>>=1;
    }
    return res;
}