組合數的求法總結

O(n^2)

楊輝三角遞推

C(i,j)=C(i−1,j)+C(i−1,j−1)

題目詳見NOIP2016D2T1

code

for(int i=;i<=maxn;i++)  
        for(int j=;j<i;j++)  
            c[i][j]=(c[i-][j]+c[i-][j-])%k;  
           

利用乘法逆元

乘法逆元： (a/b)%p=a∗(bp−2) （p為素數）

如果p為素數，那麼k的逆元就是 k(p−2)

逆元可以利用擴充歐幾裡德或歐拉函數求得

C(N,M)=N!/(M!∗(N−M)!)

那麼可以先計算出N!,M!,(N-M)!對p取模的餘數，那麼轉化為 a/b=x 的問題

因為p為素數，是以等價于 bx+py=a

然後用擴充的歐幾裡得定理算出 bx′+py′=1 的解，

x=x′∗a

就得到了最終的x的值，即 C(m,n) 得值

題目詳見雅禮集訓題目

code

ll inv(ll a){
    return a==?:(ll)(p-p/a)*inv(p%a)%p;
}

ll C(ll n,ll m){
    if(m<||n<m)return ;if(m>n-m)m=n-m;
    ll up=,down=;
    rep(i,,m-){up=up*(n-i)%p;down=down*(i+)%p;}
    return up*inv(down)%p;
}
           

Lucas求組合數

用Lucas定理求組合數，适用于模數p較小的情況

Lucas(n,m,p)=C(n%p,m%p)∗Lucas(n/p,m/p,p)

題目詳見洛谷2675

code

void work()  
    {  
        fac[]=fac[]=inv[]=inv[]=;  
        rep(i,,p-)fac[i]=fac[i-]*i%p;  //階乘預處理
        rep(i,,p-)inv[i]=(p-p/i)*inv[p%i]%p;  
        rep(i,,p-)inv[i]=inv[i-]*inv[i]%p;  //逆元預處理
    }  
    ll C(ll n,ll m)  
    {  
        if(n<m)return ;  //舍去組合數無意義的情況
        if(n<p&&m<p)return fac[n]*inv[m]%p*inv[n-m]%p;  
        return C(n/p,m/p)*C(n%p,m%p)%p;  
    }