本篇部落格來自南昌理工學院acm集訓隊成員yyj
組合數
1.定義
組合數：從 n 個不同元素中每次取出 m 個不同元素 ，不管其順序合成一組，稱為從 n 個元素中不重複地選取 m 個元素的一個組合。所有這樣的組合的種數稱為組合數。
2.性質與描述
2.1寫法
線上性寫法中被寫作C(n,m)。
組合數的計算公式為：
2.2性質
性質1.
從n個不同元素中取出m個元素的組合數 == 從n個不同元素中取出 (n-m) 個元素的組合數；
了解：
這個性質很容易了解，例如C(9,2)=C(9,7)，即從9個元素裡選擇2個元素的方法與從9個元素裡選擇7個元素的方法是相等的。
性質2：
組合恒等式 ：
若表示在 n 個物品中選取 m 個物品，則如存在下述公式：
C(n,m)=C(n,n-m)=C(n-1,m-1)+C(n-1,m)。
關于其數學證明可以看：這篇文章
dp證明：(帥哥美女必會)
如果學過一點點dp的帥哥美女都知道利用dp思想來解決問題
ex:
狀态表示：
c[i][j]表示在i個物品裡選j個的選法總數；
那麼選的狀态：選這個物品 或者 不選
選第j個物品的總數為：c[i-1][j];
不選第j個物品的總數為：c[i-1][j-1];(就是從前j-1個物品裡選)
那麼狀态方程可以表示為：
c[i][j]=c[i-1][j-1]+c[i-1][j];
3.代碼運用與解釋：
3.1說明：
在學習算法的過程中注意資料範圍是十分重要的，重要到就像有多少錢取什麼樣的老婆，在算法過程中資料範圍越大，你的錢越少，挑老婆的餘地也越少，那麼使用的方法也就越難。接下來作者本人就帶你學習一下。
3.2四大方法（有多少錢就選什麼樣的老婆）：
描述：
有a個物品，挑b個物品問有幾種選法,詢問n次。
(1)：1<=b<=a<=2000,10萬次詢問。
解法：先預處理一下(遞推)，把所有答案都預處理出來，然後直接詢問出答案。
處理方式：運用的組合恒等式 雙重循環，dp求解。
代碼如下：
// c[a][b] 表示從a個中選b個的方案數
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
時間複雜度為：O(a^2);
(2).1<=a<=b<=100000,1萬次詢問，答案太大 需要mod 1e9+7。
解法：利用逆元求解
簡單了解一下逆元：設x為a的逆元，那麼有x*a(mod p)== 1;（a要和p互質）
x稱為a模上p的逆元，那麼x可以了解為a的倒數。因為乘起來結果取模是一樣的。
逆元的求法：運用費馬小定理：
若a與p互質那麼：b^(p-1)mod§==1。
把b^(p-1)拆開來：b * b ^(p-2).
那麼b ^(p-2)就相當于x了，即為b的逆元。
但是還是有很多細節需要注意，p可能太大了，需要快速幂來求解
看代碼：
#include<iostream>
using namespace std;
const int N=1e5+10,mod=1e9+7;;
long long f[N],nf[N];
int ksm(int a,int b,int p) //快速幂
{
long long res=1;
while(b)
{
if(b&1)res=res*a%p;
a=(long long)a*a%p;
b>>=1;
}
return res;
}
int main()
{
f[0]=nf[0]=1; //0!=1,f[i]為i的階層，nf為逆元
for(int i=1;i<=N;i++)
{
f[i]=f[i-1]*i%mod;
nf[i]=nf[i-1]*ksm(i,mod-2,mod)%mod; //快速幂求逆元
}
int t;
cin>>t;
while(t--)
{
int a,b;
cin>>a>>b;
printf("%lld\n",f[a]*nf[a-b]%mod*nf[b]%mod);
}
return 0;
}
(3).1<=b<=a<=1e^18,1<=p<=1e5;
在此引入盧卡斯定理：
若p是質數，則對于任意整數 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
#include<iostream>
using namespace std;
long long ksm(long long a,long long b,long long p)
{
long long res=1;
while(b)
{
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
long long C(long long a,long long b,long long p)
{
long long res=1;
for(int i=1,j=a;i<=b;i++,j--)
{
res=res*j%p;
res=res*ksm(i,p-2,p)%p; //至于為什麼，自己想。或者是看下面的解釋
}
return res;
}
long long lucas(long long a,long long b,long long p)
{
if(a<p&&b<p)return C(a,b,p); //直接return
else return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p; //因為a/p不一定比p小，是以還是需要調用一次
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long a,b,p;
cin>>a>>b>>p;
cout<<lucas(a,b,p)<<endl;
}
}
為什麼可以這樣求解 :
Cba=a!(a−b)!∗b!=a∗(a−1)∗(a−2)∗…∗(a−b+1)∗(a−b)∗…∗1/(a−b)∗(a−b−1)∗…∗1∗b!
=a∗(a−1)∗(a−2)∗…(a−b+1)/b!
分子一共有a-(a-b)項，也就是b項。是以直接分别求階層即可。
(4).1<=a<=b<=5000,不取模
當我們需要求出組合數的真實值，而非對某個數的餘數時，分解質因數的方式比較好用：
1. 篩法求出範圍内的所有質數
2. 通過 C(a, b) = a! / b! / (a - b)! 這個公式求出每個質因子的次數。 n! 中p的次數是 n / p + n / p^2 + n / p^3 + …
3. 用高精度乘法将所有質因子相乘
#include<iostream>
using namespace std;
const int N=5010;
bool str[N];
int prime[N],c[N],res[N],x;
void muli(int b) //高精度
{
int t=0;
for(int i=1;i<=x;i++)
{
res[i]=res[i]*b+t;
t=res[i]/10;
res[i]=res[i]%10;
}
while(t)
{
res[++x]=t%10;
t=t/10;
}
while(res[x]==0&&x>0)x--;
}
int get(int a,int p) //求質因子的個數a!中質因子為p的個數
{
int t=0;
while(a)
{
t+=a/p;
a/=p;
}
return t;
}
int main()
{
int a,b;
cin>>a>>b;
for(int i=2;i<=a;i++)
{
if(str[i]==0)
for(int j=i+i;j<=a;j+=i)str[j]=true; 篩質數
}
for(int i=2;i<=a;i++)
{
if(!str[i])
{
c[i]=get(a,i);
}
}
for(int i=2;i<=b;i++)
{
if(!str[i])
{
c[i]-=get(b,i); // 減去b!的質因子
}
}
for(int i=2;i<=a-b;i++)
{
if(!str[i])
{
c[i]-=get(a-b,i); // 減去(a-b)!的質因子
}
}
res[1]=1;
x=1; //x為位數
for(int i=2;i<=a;i++)
{
for(int j=1;j<=c[i];j++)
{
muli(i);
}
}
for(int i=x;i>=1;i--)printf("%d",res[i]);
return 0;
}
作者有話說：
基礎打得好學到後面你自然學的就快，切莫狂妄自大，學習組合數運用到了很多知識點：
快速幂，高精度，篩法篩質數，逆元，費馬小定理，盧卡斯定理，dp原理，隻有擁有砸肆的基礎才能走得更高。
話不多說，認真學習的帥哥有獎勵：給你們看看漂亮小姐姐：