当前位置：首页 > news >正文

数论之组合数

news 来源：原创 2024/9/20 11:40:23

组合数1：

预处理每一个组合数的大小

类似于dp，从a个苹果里面选b个出来：首先从a个苹果里面拿出来一个，这样就分成了两种，一种是包括这个拿出来的苹果的方案数，此时就只需要拿b-1个苹果。一种是不包括这种苹果的方案数。

也就是c[a][b] = c[a-1][b] + c[a-1][b-1]

#include<bits/stdc++.h>
using namespace std;
const int N = 2010,mod = 1e7+7;
int c[N][N];// 将2000个数都预处理得到其组合数
void Init(){for(int i = 0; i < N; i++){for(int j = 0; j <= i; j++){if(!j) c[i][j] = 1;//从i个里面选0个，只有1种选法那就是不选else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}}
}int main() {Init();int n; scanf("%d",&n);while(n--){int a,b; scanf("%d %d",&a,&b);printf("%d\n",c[a][b]);}return 0;
}

组合数2：

预处理过程中的一步：阶乘

求组合数的公式：

$C_{a}^{b}\, = \frac{a!}{(a - b)!\, *\, b!}$

注意：

$\frac{a}{b}\, \,mod\, \, \, p\, \, \, != \frac{a\, \, mod\, \,p }{b \, \, \, mod p}$ 所以要化成逆元（快速幂求逆元），把除法变成乘法

时间复杂度 $N\log N$

$fact[i]\, =\, i!\,\, \, mod\, \, p$ $infact[i] = (i!)^{-1} \, \, \, mod\, \, \, p$

$C_{a}^{b}\, = \, fact[a] * infact[a - b] *infact[b]$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010,mod = 1e9 + 7;
int fact[N],infact[N];
int ksm(int a,int k,int p){int res = 1;while(k){if(k & 1) res = (ll) res * a % p;k >>= 1;a = (ll) a * a % p;}return res;
}
int main() {fact[0] = infact[0] = 1;//预处理公式中的阶乘for(int i = 1; i < N; i++){fact[i] = (ll)fact[i - 1] * i;infact[i] = (ll) infact[i - 1] * ksm(i, mod - 2, mod) % mod;}int n; cin >> n;while(n--){int a,b; cin >> a >> b;cout <<(ll) fact[a] * infact[a - b] % mod * infact[b] % mod <<'\n';}return 0;
}

组合数3：

卢卡斯定理：

结论：

卢卡斯定理的递归：

时间复杂度大约是 $p*logN*logp$

计算组合数值的C函数：

所以循环只需要执行b次即可，由于分母除法不好计算，就运用了逆元（快速幂求），和分子累乘即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int p;//快速幂计算逆元
int ksm(int a, int k) {int res = 1;while (k) {if (k & 1) res = (ll)res * a % p;k >>= 1;a = (ll)a * a % p;}return res;
}
//利用公式计算组合数
int C(int a, int b) {if (b > a) return 0;int res = 1;for (int i = 1, j = a; i <= b; i++, j--) {res = (ll)res * j % p;// 计算分子res = (ll)res * ksm(i, p - 2) % p;//计算分母的逆元}return res;
}
//卢卡斯定理
int lucas(ll a, ll b) {if (a < p && b < p) return C(a, b);return (ll)C(a % p, b % p) * lucas(a / p, b / p) % p;// 递归计算组合数模 p 的值
}int main() {int n;cin >> n;while (n--) {ll a, b;cin >> a >> b >> p;cout << lucas(a, b) << '\n';}return 0;
}

组合数4：

从定义出发，来算组合数，不需要取模

先把组合数分解质因数->实现高精度乘法

1.获取质数列表Prime

为什么需要分解质因数？

2. 计算质数在阶乘中的出现次数

get 函数计算了 n! 中质数 p 出现的总次数。这是通过逐次计算 n 中 p 的倍数出现的次数、p^2 的倍数出现的次数、p^3 的倍数出现的次数等来完成的。公式如下：

3. 计算组合数的质因数分解

组合数 C(a, b) 中各个质数 p 的幂次：每个质数 p 的幂次为 a! 中 p 的次数减去 b! 和 (a-b)! 中 p 的次数。

4. 高精度乘法计算组合数

mul 函数将高精度的大整数 a 和整数 b 相乘，并将结果存储在一个 vector<int> 中，以支持处理大数运算。结果按位存储，便于后续进一步的乘法运算。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5010;
int prime[N],cnt;
int sum[N];//每一个质数出现的次数
bool st[N];//筛法获取小于等于 n 的所有质数
void get_prime(int n)
{for(int i = 2;i <= n; i++){if(!st[i])prime[cnt++] = i;for(int j = 0; prime[j] * i <= n; j++){st[prime[j] * i]=true;if(i % prime[j]==0)break;//==0每次漏}}}
//计算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 main() {int a, b; cin >> a >> b;get_prime(a);  // 获取所有小于等于 a 的质数for(int i = 0; i < cnt; i++) {int p = prime[i];sum[i] = get(a, p) - get(a - b, p) - get(b, p); // 计算组合数公式中每个质数的幂次}vector<int> res;res.push_back(1);  // 初始化结果为 1for(int i = 0; i < cnt; i++) {for(int j = 0; j < sum[i]; j++) {res = mul(res, prime[i]);  // 依次将所有质数的幂次相乘}}for(int i = res.size() - 1; i >= 0; i--) cout << res[i];return 0;
}