首页 > 代码库 > 组合数

组合数

2024-09-06 13:56:22   216人阅读

从m个不同元素中，任取n(n≤m)个元素并成一组，叫做从m个不同元素中取出n个元素的一个组合；

从m个不同元素中取出n(n≤m)个元素的所有组合的个数，叫做从m个不同元素中取出n个元素的组合数。

 combinatorial number

技术分享  技术分享/  技术分享  技术分享 技术分享

 

 

在线性写法中被写作C(m,n)。

c(m,n)=p(m,n)/n!=m!/((m-n)!*n!)

 组合数的计算：C(n,k)有多种解法，1，dp递推；2，直接计算；3，lucas定理

 

性质：

性质1 C(n,m)= C(n,n-m)互补性质

　　例如C(9,2)=C(9,7)，即从9个元素里选择2个元素的方法与从9个元素里选择7个元素的方法是相等的。

　　规定：C(m,0)=1

性质2 C(n,m)=  C(n-1,m-1)+C(n-1,m) 组合恒等式

摘自http://blog.csdn.net/wty__/article/details/20048467

1.最简单的情况，数据比较小，直接采用C(a, b) = a * (a - 1) *....* (a - b + 1) / (b * (b - 1) *...* 2 * 1)
试用数据范围：a <= 29。在a = 30, b = 15时，计算分子乘机时即超范围

 1 LL combi(LL a,LL b)///从a中取b
 2 {
 3     if(a<b){
 4         return 0;
 5     }
 6     LL r=1;
 7     for(int i=a;i>=a-b+1;i--)
 8         r*=i;
 9     for(int j=b;j>1;j--)
10         r/=j;
11     return r;
12 }

2.采用分解质因子的方式，可以计算足够大的数（因为数字会超过long long的范围，所以结果依然用质因子表示，模板中计算出了相应的数）

 1 #include <iostream>
 2 #include "cstdio"
 3 #include "map"
 4 #include "cmath"
 5 using namespace std;
 6 #define LL long long
 7 map <int, LL> m;
 8 
 9 ///分解质因数
10 ///k为1或-1
11 void fun(int n, int k)
12 {
13     for (int i = 2; i <= sqrt(n * 1.0); i++)
14     {
15         while (n % i == 0)
16         {
17             n /= i;
18             m[i] += k;///存储因数+次数（k=-1倒数）
19         }
20     }
21     if (n > 1)
22     {
23         m[n] += k;
24     }
25 }
26 
27 ///快速幂
28 LL quick_pow(LL a, LL b)
29 {
30 
31     LL ret = 1;
32     while (b)
33     {
34         if (b & 1)
35         {
36             ret *= a;
37         }
38         b >>= 1;
39         a *= a;
40     }
41     return ret;
42 }
43 
44 ///求组合数
45 LL C(LL a, LL b)
46 {
47     if (a < b || a < 0 || b < 0)
48         return 0;
49     m.clear();
50     LL ret = 1;
51     b = min(a - b, b);
52     for (int i = 0; i < b; i++)
53     {
54         fun(a - i, 1);///分母
55     }
56     for (int i = b; i >= 1; i--)
57     {
58         fun(i, -1);///分子
59     }
60 
61     ///以下计算出了具体的数
62     for (__typeof(m.begin()) it = m.begin(); it != m.end(); it++)
63     {
64         if ((*it).second != 0)
65         {
66             ret *= quick_pow((*it).first, (*it).second);///快速幂，在之前分解质因数时 在过程+（-1）中其实已经运算了一部分，所以才不容易乘过界。
67         }
68     }
69     return ret;
70 }
71 int main()
72 {
73     LL a,b;
74     while(~scanf("%lld%lld",&a,&b)&&a&&b)
75     {
76         cout<<C(a,b)<<endl;
77     }
78 }

 

组合数


联系
我们