组合数 II
例题 1 组合数比较
题意
给定两个组合数 C(a,b) 和 C(a′,b′),比较这两个组合数的大小。
1≤b≤a≤105,1≤b′≤a′≤105。
题解
直接比较显然不行,我们可以将 C(a,b) 和 C(a′,b′) 都转换成阶乘的形式,就变成了 a!b!×(a−b)! 和 a′!b′!×(a′−b′)! 两个数作比较的形式。但是由于我们无法预处理组合数,所以依然不行。
那么我们需要一个全新的算法。现在我们给你两个自然数 a,b,∀k∈N+, 如果 ak>bk,那么 a>b。
我们有以下的公式:log C(n,m)=log n!m!(n−m)!=log n!−log m!−log (n−m)! 和 log n!=Πni=1logi。
所以我们可以将组合数用上面的公式一边算一遍开 log,然后求值就可以了。
注意浮点数的精度误差。
double pf[]; // Preprocessing factorial.
bool compare(int a, int b, int a_, int b_) {
double l = pf[a] - pf[b] - pf[n1 - m1];
double l_ = pf[a_] - pf[b_] - pf[a_ - b_];
return abs(l + eps) < l_;
}