题解

题意分析

题目要求计算两个二项式系数的比值：

• 二项式系数定义为$C(m, n) = \frac{m!}{n!(m-n)!}$
• 给定四个自然数$p, q, r, s$，需要计算$\frac{C(p,q)}{C(r,s)}$
• 所有输入数字小于$10,000$，结果不超过$100,000,000$
• 要求结果精确到小数点后$5$位

解题思路

1. 优化计算：直接计算阶乘会导致数值过大，采用交叉约分的方法
2. 对称性利用：利用$C(m,n) = C(m,m-n)$的性质减少计算量
3. 因子分解：将分子分母分解为因子列表，交叉约分避免溢出
4. 交替乘除：在计算过程中交替进行乘法和除法，控制中间结果大小

实现步骤

1. 输入处理：读取多组输入的$p,q,r,s$值
2. 对称优化：将$q$和$s$转换为较小值
3. 因子收集：
   • 收集分子的因子（来自$C(p,q)$的分子和$C(r,s)$的分母）
   • 收集分母的因子（来自$C(p,q)$的分母和$C(r,s)$的分子）
4. 排序因子：对因子进行排序以便约分
5. 交叉计算：交替进行乘除运算，控制中间结果
6. 输出结果：格式化输出最终结果

代码注释

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

double compute_binomial_division(int p, int q, int r, int s) {
    // 利用对称性减少计算量：C(m,n)=C(m,m-n)
    if (q > p - q) q = p - q;
    if (s > r - s) s = r - s;
    
    double result = 1.0;
    
    // 收集分子和分母的因子
    vector<int> numerator_factors;   // 存储分子因子
    vector<int> denominator_factors; // 存储分母因子
    
    // C(p,q)的分子部分：p×(p-1)×...×(p-q+1)
    for (int i = p; i > p - q; --i) {
        numerator_factors.push_back(i);
    }
    
    // C(r,s)的分母部分：s!×(r-s)!，加入分子
    for (int i = 1; i <= s; ++i) {
        numerator_factors.push_back(i);
    }
    for (int i = 1; i <= r - s; ++i) {
        numerator_factors.push_back(i);
    }
    
    // C(p,q)的分母部分：q!×(p-q)!，加入分母
    for (int i = 1; i <= q; ++i) {
        denominator_factors.push_back(i);
    }
    for (int i = 1; i <= p - q; ++i) {
        denominator_factors.push_back(i);
    }
    
    // C(r,s)的分子部分：r×(r-1)×...×(r-s+1)，加入分母
    for (int i = r; i > r - s; --i) {
        denominator_factors.push_back(i);
    }
    
    // 对因子排序以便约分
    sort(numerator_factors.begin(), numerator_factors.end());
    sort(denominator_factors.begin(), denominator_factors.end());
    
    // 交叉约分计算
    int num_idx = 0, denom_idx = 0;
    int num_size = numerator_factors.size(), denom_size = denominator_factors.size();
    
    // 交替进行乘法和除法，防止中间结果过大
    while (num_idx < num_size && denom_idx < denom_size) {
        if (result > 1.0) {
            if (denom_idx < denom_size) {
                result /= denominator_factors[denom_idx++];
            }
        } else {
            if (num_idx < num_size) {
                result *= numerator_factors[num_idx++];
            }
        }
    }
    
    // 处理剩余分子因子
    while (num_idx < num_size) {
        result *= numerator_factors[num_idx++];
    }
    
    // 处理剩余分母因子
    while (denom_idx < denom_size) {
        result /= denominator_factors[denom_idx++];
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);
    
    int p, q, r, s;
    // 读取多组输入直到EOF
    while (cin >> p >> q >> r >> s) {
        double res = compute_binomial_division(p, q, r, s);
        // 设置输出精度为小数点后5位
        cout << fixed << setprecision(5) << res << "\n";
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：主要取决于$q$和$s$的大小，最坏情况下为$O(max(q,s)^2)$
• 空间复杂度：$O(max(q,s))$，用于存储因子列表