[组合] 组合数计算四大算法模板(模板+卢卡斯定理) |
您所在的位置：网站首页 › 大C计算方法 › [组合] 组合数计算四大算法模板(模板+卢卡斯定理) |
[组合] 组合数计算四大算法模板(模板+卢卡斯定理)
|
文章目录
0. 前言1. 预处理组合数+组合递推式2. 预处理阶乘+逆元3. 卢卡斯定理4. 高精度组合数
0. 前言
组合数求解有很多种方式，不同的方式对应这不同的时间复杂度，难以程度也是不尽相同。根据数据范围选择对应的方法即可。 1. 预处理组合数+组合递推式885. 求组合数 I 组合公式： C a b = ( a b ) = a × ( a − 1 ) × ⋯ × ( a − b + 1 ) 1 × 2 × 3 × ⋯ × b = a ! b ! ( a − b ) ! C_{a}^{b}=\tbinom{a}{b}=\frac {a\times(a-1)\times\cdots\times(a-b+1)} {1\times 2 \times 3 \times\cdots \times b}=\frac {a!} {b!(a-b)!} Cab=(ba)=1×2×3×⋯×ba×(a−1)×⋯×(a−b+1)=b!(a−b)!a! 时间复杂度分析： 10w 组询问一个组合数最坏需要 2000 次运算则暴力总共的时间复杂度为 2000 * 10w，为 2 亿次运算，这妥妥的超时。但是能发现，a、b 都比较小，总共可能出现的 (a,b) 对就是 2000 * 2000 = 400w 对不同的 C a b C_a^b Cab所以可以预处理出来所有的情况，有组合递推式为 C a b = C a − 1 b + C a − 1 b − 1 C_a^b=C_{a-1}^b +C_{a-1}^{b-1} Cab=Ca−1b+Ca−1b−1从实际出发， C a b C_a^b Cab 表示从 a a a 个苹果当中选 b b b 个苹果的方案数，那么可以将所有选法分为两种情况，即从 n n n 个苹果中挑出来一个苹果，这个苹果被选中，这个苹果不被选中，就这两种情况。 则包含这个特殊苹果的方案数就是 C a − 1 b − 1 C_{a-1}^{b-1} Ca−1b−1，不包含这个特殊苹果的方案数是 C a − 1 b C_{a-1}^{b} Ca−1b #include using namespace std; typedef long long LL; const int N = 2010, MOD = 1e9+7; int n; int c[N][N]; void init() { for (int i = 0; i int a, b; cin >> a >> b; cout 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 int a, b; cin >> a >> b; cout if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } // 定义求解 int C(int a, int b, int p) { if (b > a) return 0; int res = 1; for (int i = 1, j = a; i // 注意LL参数类型 if (a LL a, b, p; cin >> a >> b >> p; cout if (!st[i]) primes[cnt ++] = i; for (int j = 0; primes[j] int res = 0,t = p; while (n >= p) { res += n / p; p *= t; } return res; } // 精炼简介，完美版本 int get1(int n, int p) { int res = 0; while (n) { res += n / p; n /= p; } return res; } vector mul(vector a, int b) { vector C; int t = 0; for (int i = 0; i C.push_back(t % 10); t /= 10; } return C; } int main() { int a, b; cin >> a >> b; get_primes(a); for (int i = 0; i |
重点： 组合公式、组合递推式【本文地址】
今日新闻 |
推荐新闻 |