求组合数（取模）的两种方法

2024-03-11 05:13| 来源: 网络整理| 查看: 265

#概述首先我们要知道什么是组合数。具体可以参考我之前的博客 “排列与组合”笔记中，集合的组合的部分。

这里复述如下：令r为非负整数。我们把n个元素的集合S的r-组合理解为从S的n个元素中对r个元素的无序选择。换句话说，S的一个r-组合是S的一个子集，该子集由S的n个元素中的r个组成，即S的一个r-元素子集。

由此，求解组合数即变成了求式子C(n, r) 的值。

#法一：Pascal公式打表由Pascal公式（参考组合数学笔记之二——二项式系数），我们知道 { C ( n , k ) = C ( n − 1 , k − 1 ) + C ( n − 1 , k ) C ( n , 0 ) = C ( n , n ) = 1 \left\{ \begin{aligned} C(n, k) = ;\ C(n - 1, k - 1) + C(n - 1, k) \\ C(n, 0) = ;\ C(n, n) = 1 \end{aligned} \right. {C(n,k)=C(n,0)= C(n−1,k−1)+C(n−1,k) C(n,n)=1 取二维数组 tC[][] ，初始化 tC[0][0] = 1; 打表即可。代码最简单，如下：

const int maxn(1005), mod(100003); int tC[maxn][maxn]; //tC 表示 table of C inline int C(int n, int k) { if(k > n) return 0; return tC[n][k]; } void calcC(int n) { for(int i = 0; i < n; i++) { tC[i][0] = 1; for(int j = 1; j < i; j++) tC[i][j] = (C(i - 1, j - 1) + C(i - 1, j)) % mod; tC[i][i] = 1; } }

计算 C ( n , k ) C(n, k) C(n,k) 返回内联函数 C ( n , k ) C(n, k) C(n,k) 的值即可。

当然我们知道 C ( n , k ) = C ( n , n − k ) C(n, k) = C(n, n - k) C(n,k)=C(n,n−k) ，所以上面的代码有很多空间和时间的浪费。可以将 tC[][] 二维数组转化为一维数组存储，同时，当 j ; i / 2 j ; i / 2 j>i/2 时终止第二层循环，新代码如下：

const int maxn(10005), mod(100003); int tC[maxn * maxn]; //tC 表示 table of C inline int loc(int n, int k) // C(n, k)返回在一维数组中的位置 { int locate = (1 + (n >> 1)) * (n >> 1); // (n >> 1) 等价于 (n / 2) locate += k; locate += (n & 1) ? (n + 1) >> 1 : 0; // (n & 1) 判断n是否为奇数 return locate; } inline int C(int n, int k) { if(k > n) return 0; k = min(n - k, k); return tC[loc(n, k)]; } void calcC(int n) { for(int i = 0; i < n; i++) { tC[loc(i, 0)] = 1; for(int j = 1, e = i >> 1; j >= 1; } return ans; } LL niYuan(LL a, LL b) //费马小定理求逆元 { return pow(a, b - 2, b); } LL C(LL a, LL b) //计算C(a, b) { if(a < b) return 0; return Jc[a] * niYuan(Jc[b], mod) % mod * niYuan(Jc[a - b], mod) % mod; }

以上即为逆元求取组合数的方法，无论使用拓展欧几里得还是费马小定理，一开始求取Jc数组是的复杂度是 O ( n ) O(n) O(n)，拓展欧几里得算法和费马小定理的复杂度均为 O ( l g ( m o d ) ) O(lg(mod)) O(lg(mod)) , 如果要求取m次组合数，则总的时间复杂度为 O ( m n l g ( m o d ) ) O(mnlg(mod)) O(mnlg(mod)).

以上です。

【本文地址】

求组合数（取模）的两种方法

求组合数（取模）的两种方法

今日新闻

推荐新闻