【OI学习笔记】组合数学

板块：组合数学
前置知识点：排列组合数的概念和公式、乘法逆元、扩展欧几里得算法、费马小定理、二项式定理
难度：中等
前置知识一览：

• 排列数：在 $n$ 个元素中取出 $m$ 个元素形成一个排列的总方案数为排列数，因此排列数考虑顺序。排列数的公式为 A n m = n ( n − 1 ) ( n − 2 ) ( n − 3 ) . . . ( n − m + 2 ) ( n − m + 1 ) = n ! ( n − m ) ! . A_n^m=n(n-1)(n-2)(n-3)...(n-m+2)(n-m+1)=\frac{n!}{(n-m)!}. Anm​=n(n−1)(n−2)(n−3)...(n−m+2)(n−m+1)=(n−m)!n!​.
• 组合数：在 $n$ 个元素中取出 $m$ 个元素合为一组的总方案数为组合数，因此组合数不考虑顺序。组合数的公式为 C n m = n ( n − 1 ) ( n − 2 ) ( n − 3 ) . . . ( n − m + 2 ) ( n − m + 1 ) m ( m − 1 ) ( m − 2 ) ( m − 3 ) . . . × 2 × 1 = n ! m ! ( n − m ) ! C_n^m=\frac{n(n-1)(n-2)(n-3)...(n-m+2)(n-m+1)}{m(m-1)(m-2)(m-3)...\times 2\times 1}= \frac{n!}{m!(n-m)!} Cnm​=m(m−1)(m−2)(m−3)...×2×1n(n−1)(n−2)(n−3)...(n−m+2)(n−m+1)​=m!(n−m)!n!​
• 乘法逆元：【学习笔记】数论-乘法逆元
• 费马小定理： a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1(mod \ p) ap−1≡1(mod p)
• 二项式定理： ( 1 + x ) n = C n 0 + C n 1 x + C n 2 x 2 + . . . + C n n x n (1+x)^n=C_n^0+C_n^1x+C_n^2x^2+...+C_n^nx^n (1+x)n=Cn0​+Cn1​x+Cn2​x2+...+Cnn​xn
• 扩展欧几里得算法：待补充

一般在信息学竞赛中更多的是使用展开式，计算起来会更加容易，码量也会小一些，这点相信运用过排列组合公式的同学都有所体会。

组合数学是信息学竞赛的重要组成部分，在数学推导题中发挥着重要作用，相关公式、概念、定理都在考纲之中。本文将陈述组合数计算的五种情况。本文中一律设定模数 M O D = 1 0 9 + 7 MOD=10^9+7 MOD=109+7。

组合数计算的四种情况

组合数的计算方法有很多，例如定义式法、杨辉三角公式法、卢卡斯定理等（相关公式也将在后文叙述），这些方法的使用是由数据范围决定的。

求组合数 I

理论可支持数据范围： $m\le n\le 3000$
时间复杂度： O ( n 2 ) O(n^2) O(n2)
求解方法：杨辉三角公式（人教A版高中数学教材选修3 P39）

在该级别的数据范围下，可以直接将组合数数组预处理出来，然后 $O(1)$ 查询，时间上和空间上都可行（指在仅求解组合数的情况下）。那么就涉及到一个大名鼎鼎的公式了——杨辉三角公式（如下）。
C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1} Cnm​=Cn−1m​+Cn−1m−1​
关于该式的正确性，教材上有较为详细的证明，这里我简要描述一下：
C n − 1 m − 1 + C n − 1 m = ( n − 1 ) ! ( m − 1 ) ! ( n − m ) ! + ( n − 1 ) ! m ! ( n − m − 1 ) ! = ( n − 1 ) ! m ! ( n − m ) ! [ r + ( n − r ) ] = n ! m ! ( n − m ) ! C_{n-1}^{m-1}+C_{n-1}^{m}=\frac{(n-1)!}{(m-1)!(n-m)!}+\frac{(n-1)!}{m!(n-m-1)!}\\ =\frac{(n-1)!}{m!(n-m)!}[r+(n-r)]\\ =\frac{n!}{m!(n-m)!} Cn−1m−1​+Cn−1m​=(m−1)!(n−m)!(n−1)!​+m!(n−m−1)!(n−1)!​=m!(n−m)!(n−1)!​[r+(n−r)]=m!(n−m)!n!​
又，
C n m = n ! m ! ( n − m ) ! C_{n}^{m}=\frac{n!}{m!(n-m)!} Cnm​=m!(n−m)!n!​
因此该式正确。

直接两层循环预处理，对于 $m=0$ 的情况特判防止数组越界， C n 0 = 1 C_n^0=1 Cn0​=1。

参考代码：

#include 
#include using namespace std;const int N = 2010, MOD = 1e9 + 7;int n;
int c[N][N];void pretreatment ()
{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;}}
}int main()
{pretreatment();cin >> n;while (n--){int a, b;cin >> a >> b;cout << c[a][b] << endl;}return 0;
}

求组合数 II

理论可支持数据范围： m ≤ n ≤ 1 0 5 m\leq n\leq10^5 m≤n≤105
时间复杂度：$O(nlogn)$
求解方法：定义式法

在该数据范围内， O ( n 2 ) O(n^2) O(n2) 的预处理显然会超时，那么我们就要降低时间复杂度到对数级，也就是 $O(nlogn)$级别。考虑线性预处理数据范围内的所以阶乘结果，以供查询。由于组合数公式中需要除以 $m!$，我们可以将其转化为计算 $m!$ 的乘法逆元，因为在这里我们用费马小定理计算（因为设定模数为质数，当然如果实际题目中给定的模数不是质数则需要用扩欧计算逆元，详解文首链接），费马小定理计算乘法逆元的时间复杂度为 $O(logn)$，因此总复杂度为 $O(nlogn)$。

综上，我们用一个数组 fact 记录所有的阶乘结果，用一个数组 infact 记录所有阶乘结果的逆元，最后查询时就是 m ! × ( n − m ) ! − 1 × m − 1 m!\times (n-m)!^{-1}\times m^{-1} m!×(n−m)!−1×m−1。

参考代码：

#include 
#include using namespace std;typedef long long ll;const int N = 1e5 + 10, MOD = 1e9 + 7;int n;
int fact[N], infact[N];int qmi(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (ll)res * a % p;a = (ll)a * a % p;k >>= 1;}return res;
}int main()
{fact[0] = infact[0] = 1;for (int i = 1; i < N; i++){fact[i] = (ll)fact[i - 1] * i % MOD;infact[i] = (ll)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD;}cin >> n;while (n--){int a, b;cin >> a >> b;cout << (ll)fact[a] * infact[b] % MOD * infact[a - b] % MOD<< endl;}return 0;
}

求组合数 III

理论可支持数据复杂度： m ≤ n ≤ 1 0 18 m\leq n\leq 10^{18} m≤n≤1018
时间复杂度： O ( p l o g p N log ⁡ p ) O(p\ log_pN\log\ p) O(p logp​Nlog p)
求解方法：卢卡斯（Lucas）定理

到了该级别的数据范围，我们需要将时间复杂度继续压缩，压缩到上述的时间复杂度中，那么就涉及到了一个更加有名的定理——卢卡斯定理（如下）。
C a b ≡ C a m o d b b m o d p × C a / p b / p ( m o d p ) C_a^b\equiv C_{a\bmod b}^{b\bmod p}\times C_{a/ p}^{b/p}(\bmod\ p) Cab​≡Camodbbmodp​×Ca/pb/p​(mod p)
关于该式的证明（拓展）：
将 $a,b$ 表示为 $p$ 进制数得：
a = a k p k + a k − 1 p k − 1 + a k − 2 p k − 2 + . . . + a 0 p 0 b = b k p k + b k − 1 p k − 1 + b k − 2 p k − 2 + . . . + b 0 p 0 a=a^kp^k+a^{k-1}p^{k-1}+a^{k-2}p^{k-2}+...+a^0p^0\\ b=b^kp^k+b^{k-1}p^{k-1}+b^{k-2}p^{k-2}+...+b^0p^0 a=akpk+ak−1pk−1+ak−2pk−2+...+a0p0b=bkpk+bk−1pk−1+bk−2pk−2+...+b0p0
有二项式定理，
( 1 + x ) p = C p 0 + C p 1 x + C p 2 x 2 + C p 3 x 3 + . . . + C p p x p ① (1+x)^p=C_p^0+C_p^1x+C_p^2x^2+C_p^3x^3+...+C^p_px^p① (1+x)p=Cp0​+Cp1​x+Cp2​x2+Cp3​x3+...+Cpp​xp①
因为模数 $p$ 是一个质数，所以 $p$ 里面不包含任何小于 $p$ 的质因子。因此展开式中除头尾两项外，其余项均为 0，即 ( 1 + x ) p ≡ ( 1 + x p ) ( m o d p ) , 同理可得 ( 1 + x p i ) ≡ ( 1 + x p i ) ( m o d p ) ② (1+x)^p\equiv (1+x^p) (\bmod\ p),同理可得(1+x^{p_i})\equiv (1+x^{p_i})(\bmod \ p)② (1+x)p≡(1+xp)(mod p),同理可得(1+xpi​)≡(1+xpi​)(mod p)②

又当 $p=a$ 时，由同底数幂乘法的定义可以得：
( 1 + x ) a = ( 1 + x ) a 0 [ ( 1 + x ) p 1 ] a 1 [ ( 1 + x ) p 2 ] a 2 . . . [ ( 1 + x ) p k ] a 1 (1+x)^a=(1+x)^{a_0}[(1+x)^{p_1}]^{a_1}[(1+x)^{p_2}]^{a_2}... [(1+x)^{p_k}]^{a_1} (1+x)a=(1+x)a0​[(1+x)p1​]a1​[(1+x)p2​]a2​...[(1+x)pk​]a1​
带入 $②$ 式可得：
( 1 + x ) a = ( 1 + x ) a 0 ( 1 + x p ) a 1 ( 1 + x p 2 ) a 2 ( 1 + x p 2 ) a 2 (1+x)^a=(1+x)^{a_0}(1+x^p)^{a_1}(1+x^{p_2})^{a_2}(1+x^{p_2})^{a_2} (1+x)a=(1+x)a0​(1+xp)a1​(1+xp2​)a2​(1+xp2​)a2​
观察 $①$ 式，可知对于 x i x_i xi​ ，其系数为 C a i C_a^i Cai​，所以可得：
C a b ≡ C a k b k C a k − 1 b k − 1 C a k − 2 b k − 2 . . . C a 0 b 0 ( m o d p ) C_a^b\equiv C_{a_k}^{b_k}C_{a_{k-1}}^{b_{k-1}}C_{a_{k-2}}^{b_{k-2}}...C_{a_{0}}^{b_{0}}(\bmod\ p) Cab​≡Cak​bk​​Cak−1​bk−1​​Cak−2​bk−2​​...Ca0​b0​​(mod p)
其实关键证明到这里就完毕了，接下来是化简。

在证明之首我们已经将 $a,b$ 化为了 $p$ 进制数，所以有 a 0 = a m o d p , b 0 = b m o d p ③ a_0=a\bmod\ p,b_0=b\bmod\ p③ a0​=amod p,b0​=bmod p③，我们将 $a,b$ 在 $p$ 进制下右移一位，等价于 ⌊ a p ⌋ , ⌊ b p ⌋ \lfloor \frac{a}{p}\rfloor,\lfloor \frac{b}{p}\rfloor ⌊pa​⌋,⌊pb​⌋，对于 ⌊ a p ⌋ , ⌊ b p ⌋ \lfloor \frac{a}{p}\rfloor,\lfloor \frac{b}{p}\rfloor ⌊pa​⌋,⌊pb​⌋重复证明中的第一步，可以得到 C ⌊ a p ⌋ ⌊ b p ⌋ ≡ C a k b k C a k − 1 b k − 1 C a k − 2 b k − 2 . . . C a 1 b 1 ( b m o d p ) C_{\lfloor \frac{a}{p}\rfloor}^{\lfloor \frac{b}{p}\rfloor}\equiv C_{a_{k}}^{b_{k}}C_{a_{k-1}}^{b_{k-1}}C_{a_{k-2}}^{b_{k-2}}...C_{a_{1}}^{b_{1}}(b\ mod\ p) C⌊pa​⌋⌊pb​⌋​≡Cak​bk​​Cak−1​bk−1​​Cak−2​bk−2​​...Ca1​b1​​(b mod p)
因此得证：
C a b ≡ C ⌊ a p ⌋ ⌊ b p ⌋ × C a m o d p b m o d p ( m o d p ) C_a^b\equiv C_{\lfloor \frac{a}{p}\rfloor}^{\lfloor \frac{b}{p}\rfloor}\times C_{a\bmod p}^{b\bmod p}(\bmod\ p) Cab​≡C⌊pa​⌋⌊pb​⌋​×Camodpbmodp​(mod p)

在代码应用卢卡斯定理时候，对于 a , b < p a,b

a,b<p 的情况，$\mathrm{mod}p$ 操作做与不做都会保持原值，因此可以直接返回 C a b C_a^b Cab​。否则，返回 C a m o d p b m o d p × l u c a s ( a / p , b / p ) C_{a\bmod p}^{b\bmod p}\times lucas(a/p,b/p) Camodpbmodp​×lucas(a/p,b/p)，因为 $a/p,b/p$的结果仍可能超出 $p$ 的值，所以需要递归计算。

计算 C a b C_a^b Cab​ 我们仍套用“前置知识一览”中的展开式，用双指针算法（详见代码，比较巧妙），初始化 $i=1,j=n$，以 $i\le m$ 为循环结束条件，那么 $j$ 也将循环到 $n-m+1$。

参考代码：

#include 
#include using namespace std;typedef long long ll;int p;int qmi (int a, int b)
{int res = 1;while (b){if (b & 1) res = (ll)res * a % p;a = (ll)a * a % p;b >>= 1;}return res;
}int C (int n, int m)
{int res = 1;for (int i = 1, j = n; i <= m; i++, j--){res = (ll)res * j % p;res = (ll)res * qmi (i, p - 2) % p;}return res;
}ll lucas (ll a, ll b)
{if (a < p && b < p) return C (a, b);else return C (a % p, b % p) * lucas (a / p, b / p) % p;
}int n;int main()
{cin >> n;for (int i = 1; i <= n; i++){ll a, b;cin >> a >> b >> p;cout << lucas (a, b) << endl;}return 0;
}

求组合数 IV

参考资料：https://www.acwing.com/solution/content/132647/

理论可支持数据范围：$m\le n\le 5000$，无模数
时间复杂度： O ( n 2 ) O(n^2) O(n2)
求解方法：线性筛+质因数分解+高精度

该方法分为三步：

• 线性筛法求出 $1\sim n$ 中的所有质数
• 考虑从组合数公式 C a b = a ! b ! ( a − b ) ! C_a^b=\frac{a!}{b!(a-b)!} Cab​=b!(a−b)!a!​ 出发，求出每个质因子的次数。
• 用高精度乘法将所有质因子相乘

求阶乘中质因子的次数：
对于步骤二中的每一项，$n/p$ 表示阶乘的每一位中拆开至少有 1 个 $p$ 的数的个数。因为除去 $n/p$ 只计算了分解后包含 $p$ 的数的个数，而有些数分解后是包含多个 $p$ 的，因此有了后面几项，一直算到除数大于 $n$ 为止。

$ex：7!$
假设 $p$ 为 2，$7/2$ 表示 2,4,6 这3个数，因为我们要先把不被 $p$ 整除的数扔掉。其中 4 拆开是两个 2，因此在下一步中 $7/4$ 中再算了一次 4，所以因式分解 7！ 后 2 的次数为 4.

那会不会出现上下素数出现次数相减为负数的情况呢？
我们根据组合数公式展开式 C a b = a ( a − 1 ) ( a − 2 ) . . . ( a − b + 1 ) b ! C_a^b=\frac{a(a-1)(a-2)...(a-b+1)}{b!} Cab​=b!a(a−1)(a−2)...(a−b+1)​ 进行推导。

利用反证法，我们假设存在这样一个素数，那么在上面这个式子里， $p$ 在 $1\sim b$ 之间，并且 $p$ 的倍数不在上式的分子内，即：
$$\exists t,s.t.a<(t+1)p,a-b+1>tp$$
而 $p$ 小于 $b$，因此：
$$a>tp+b-1>(t+1)p-1$$
所以：
$$(t+1)p>a>(t+1)p-1$$
由此可知，不存在整数 $a$ 满足这个条件，发生矛盾，所以不会出现该情况

参考代码：

#include 
#include 
#include using namespace std;const int N = 5000;int primes[N], cnt;
int sum[N];
bool st[N];//线性筛
void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}//获取n!里的p的个数
int get (int n, int p)
{int res = 0;while (n){res += n / p;n /= p;}return res;
}vector<int> mul(vector<int> a, int b)
{vector<int> c;int t = 0;for (int i = 0; i < a.size(); i++){t += a[i] * b;c.push_back(t % 10);t /= 10;}while (t){c.push_back(t % 10);t /= 10;}return c;
}int a, b;int main()
{cin >> a >> b;get_primes(a);for (int i = 0; i < cnt; i++){int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a - b, p);}vector<int> res;res.push_back(1);for (int i = 0; i < cnt; i++){for (int j = 0; j < sum[i]; j++){res = mul(res, primes[i]);}}for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！