UVa 530 Binomial Showdown

题目描述题目要求计算组合数C(n,k)C(n, k)C(n,k)。输入包含多个测试用例每行两个整数nnn和kkk输入以0 0结束。输出每个组合数的值结果保证在323232位有符号整数范围内小于2312^{31}231。输入格式输入包含多行每行两个整数nnn和kkk。输入以0 0结束。输出格式对于每个测试用例输出一行一个整数表示C(n,k)C(n, k)C(n,k)。样例输入4 2 10 5 49 6 0 0输出6 252 13983816题目分析本题的核心是计算组合数C(n,k)n!k!(n−k)!C(n, k) \frac{n!}{k!(n-k)!}C(n,k)k!(n−k)!n!​需要避免中间结果溢出。计算方法使用乘法累积并约分的方法C(n,k)∏i1kn−kii C(n, k) \prod_{i1}^{k} \frac{n - k i}{i}C(n,k)i1∏k​in−ki​在计算过程中每次乘以分子后与分母中的数约分确保中间结果不超过最终结果的大小。算法步骤若kn/2k n/2kn/2令kn−kk n - kkn−k利用对称性。初始化分子数组为[n,n−1,…,n−k1][n, n-1, \ldots, n-k1][n,n−1,…,n−k1]分母数组为[1,2,…,k][1, 2, \ldots, k][1,2,…,k]。对每个分子和分母求最大公约数约分。将约分后的分子相乘得到结果。复杂度分析时间复杂度O(k2log⁡n)O(k^2 \log n)O(k2logn)k≤nk \le nk≤n可接受。代码实现// Binomial Showdown// UVa ID: 530// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intgcd(inta,intb){intt;while(a%b)ta,ab,bt%b;returnb;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,k;while(cinnk,n||k){if(kn/2)kn-k;vectorintup,down;for(inti1;ik;i){up.push_back(n-i1);down.push_back(i);}for(inti0;ik;i)for(intj0;jk;j)if(up[i]1down[j]1){intdividergcd(up[i],down[j]);if(divider1)up[i]/divider,down[j]/divider;}longlongintnumber1;for(inti0;ik;i)if(up[i]1)number*up[i];coutnumber\n;}return0;}