组合数 $\rm{II}$

例题 $\large\it{1}$ 组合数比较

题意

给定两个组合数 $\mathcal C(a, b)$ 和 $\mathcal C(a’, b’)$，比较这两个组合数的大小。

$1\le b\le a\le 10^5$，$1\le b’\le a’\le 10^5$。

题解

直接比较显然不行，我们可以将 $\mathcal C(a, b)$ 和 $\mathcal C(a’, b’)$ 都转换成阶乘的形式，就变成了 $\dfrac{a\tt{!}}{b{\tt{!}}\times (a-b)\tt{!}}$ 和 $\dfrac{a’\tt{!}}{b’{\tt{!}}\times (a’-b’)\tt{!}}$ 两个数作比较的形式。但是由于我们无法预处理组合数，所以依然不行。

那么我们需要一个全新的算法。现在我们给你两个自然数 $a$，$b$，$\forall k\in N^+$, 如果 $\cfrac{a}{k}\gt \cfrac{b}{k}$，那么 $a\gt b$。

我们有以下的公式：$\tt{\log\ C(n, m) = \log\ \dfrac{n\tt{!}}{m{\tt{!}}(n-m)\tt{!}}} = \log\ n\tt{!} - \log\ m\tt{!} - \log\ (n-m)\tt{!}$ 和 $\large \log\ n{\tt{!}} = \Pi_{i=1}^n \log\; i$。

所以我们可以将组合数用上面的公式一边算一遍开 $\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_;
}