组合数(Combinatorial_Number)
定義:
從n個不同元素中,任取m(m≤n)個元素并成一組,叫做從n個不同元素中取出m個元素的一個組合;從n個不同元素中取出m(m≤n)個元素的所有組合的個數,叫做從n個不同元素中取出m個元素的組合數。
公式:
在線性寫法中被寫作C(m,n)。
c(m,n)=p(m,n)/n!=m!/((m-n)!*n!)
性質:
1.互補性質
組合數性質如右圖所示:
即從m個不同元素中取出n個元素的組合數=從m個不同元素中取出(m-n)個元素的組合數
這個性質很容易理解,例如C(9,2)=C(9,7),即從9個元素里選擇2個元素的方法與從9個元素里選擇7個元素的方法是相等的。
規定:C(m,0)=1
2.組合恒等式
若表示在n個物品中選取m個物品,則如存在下述公式: C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)
求法:
1、一般方法
直接套公式:
求出m!、n!、(m-n)!然后帶人公式;
代碼如下:
# include<stdio.h> # include<math.h> int f(int n){int i,m=1;for(i=1;i<=n;i++){m=m*i;}return m; } int main(){int n,m;scanf("%d %d",&n,&m);printf("%d\n",f(n)/(f(m)*f(n-m)));return 0; }稍微用點小技巧
long long C(int n,int m) {if(m<n-m) m=n-m;long long ans=1;for(int i=m+1;i<=n;++i) ans*=i;for(int i=1;i<=n-m;++i) ans/=i;return ans; }?
2、楊輝三角
就算是long long最多20!左右;再大就會爆了
那就用到我們大數學家楊輝的三角了
: C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)
#include<iostream> using namespace std; long long c[100][100]; inline void get_it(int n) {c[0][0]=1;for (int i=1;i<=n;i++)for (int j=0;j<=i;j++)if (i==j ||j==0) c[i][j]=1;else c[i][j]=c[i-1][j]+c[i-1][j-1]; } int main() {get_it(60);for (int i=1;i<=60;i++){for (int j=1;j<=i;j++)cout<<c[i][j]<<" ";cout<<endl;} }理論上只要數組開的出來都可以,最多,emmm,反正比一般方法強。?
3、快速組合數
這個要用快速冪:https://blog.csdn.net/weixin_43272781/article/details/85058595
主要是用在一般方法;求階乘的時候。
我就不寫了。
4、求余組合數
以上方法最多也就到long long的極限,當然超過long long的我們也存儲不下了,但是如果我們只需要一部分高階組合數,用楊輝三角太浪費了吧。而且一般題目會有求余的要求,那么接下來就是大招了。
證明:https://blog.csdn.net/arrowlll/article/details/52629448
?1).擴展歐幾里德:b*x+p*y=1 有解,x就是所求2).費馬小定理:b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2)
1. n!/(m!*(n-m)! =x%p ,先對算出n!、m!、(n-m)!對p取模的余數,就轉換為a/b=x%p;因為p為素數,所以等價于bx+py=a;然后用擴展的歐幾里得定理算出 bx’+py’=1的解,x=x’*a,就得到了最終的x的值,即C(m,n)%p得值。
2.逆元 其實如果mod是素數 則b的逆元其實就是b^(mod-2)?
也就是 (m!(n-m)!)的逆元為 (m!(n-m)!)p-2 ;
3.當n和m比較大,mod是素數且比較小的時候(10^5左右),通過Lucas定理計算
Lucas定理:A、B是非負整數,p是質數。A B寫成p進制:A=a[n]a[n-1]…a[0],B=b[n]b[n-1]…b[0]。?
則組合數C(A,B)與C(a[n],b[n])C(a[n-1],b[n-1])…*C(a[0],b[0]) mod p同余?
即:Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p)
C(n % mod, m % mod) % mod; 如果太大還是利用上面的逆元來處理。
半預處理?
由于Lucas定理保證了階乘的數均小于p,所以可以講所有的階乘先預處理,優化C(n,m)?
mod的要求:p<10^6,且為素數?
有效范圍:1<=n,m<=10^9
例題
https://blog.csdn.net/weixin_43272781/article/details/85269419
?
?
總結
以上是生活随笔為你收集整理的组合数(Combinatorial_Number)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Make It Connected
- 下一篇: Polygon for the Angl