这是一个非常简单的程序，有 t 个测试用例，我们必须找到 nCr=n!/r!*(n-r)!。
所以它适用于较小的值，如 20C2，但不适用于较大的值，如 100C10。它给出 32C2=-6 ,100C10 浮点异常。
如何做到 1<=n<=r<=1000 ？
注意:我不是在要求 long double 或不想将其更改为 float。答案应该类似于 100C10 = 17310309456440 和 989C45=?
#include<iostream>
using namespace std;
long long int fact(long long int num);
int main()
{
int t;
cin>>t;
long long int n[1000],r[1000],c[1000];
for(int i=0;i<t;i++)
{
cin>>n[i];
cin>>r[i];
}
for(int i=0;i<t;i++)
{
c[i]=fact(n[i])/(fact(r[i])*fact(n[i]-r[i])) ;
cout<<c[i];
}
return 0;
}
long long int fact(long long int num){
long long int k;
if(num==0)
num=1;
else
{
for(k=num-1;k>0;k--)
num=num*k;
}
return num;
}
是时候接触一下数学了:
nCr = fact(n)/(fact(r)*fact(n-r))
一个例子使这更容易，让我们做 5C3:
5C3 = fact(5)/(fact(3)*fact(5-3))
= fact(5)/(fact(3)*fact(2))
= 5x4x3x2x1 / (3x2x1 * 2x1)
= 5x4 / 2x1
所以我们可以看到一些因素会抵消；如果完整的 fact(n) 会溢出，这将非常有用。
定义一个范围阶乘:
rafa(a,b) = a*(a-1)*...*(b+1)*b where a > b
= product(b..a)
然后
rafa(n,r) = fact(n)/fact(r)
-> nCr = rafa(n,r) / fact(r)
我们可以到此为止，这样我们就可以显着扩大 n 和 r 的值集，我们可以在不溢出的情况下计算这些值。
加分
通过 rafa(n,r) 和 fact(r)，我们可以看到当 r 几乎与 n，则问题的大部分规模将取消。所以 100C97 = 100x99x98/3x2x1 = 100x33x49。
然后考虑一个因子匹配算法(类似于 python 的伪代码):
numerElems = [100,99,98]
initialDenomElems = [3,2,1]
# cancelFactors modifies numerElems values, returns un-cancelled denominator elements
def cancelFactors(numerElems, denomElems):
finalDenomElems = []
for denom in denomElems:
for factor in factorise(denom):
for idx,numer in enumerate(numerElems):
if isFactorOf(factor, numer):
numerElems[idx] = numer/factor
else
finalDenomElems.push(factor)
return finalDenomElems;
然后您可以对分子元素的乘积除以剩余分母元素的乘积进行最终计算。因为我们知道 nCr 总是返回一个整数结果，所以我们知道当使用 cancelFactors 时它总是会取消所有的因素。因此该算法最大化不溢出的n,r对的可能空间。但是写的是O(n^3 * f)，其中f是得到一个整数的所有因子的代价，所以不会很快。但是，对于较大的 n 和 r 值，这可能是不使用不同类型来计算结果的唯一方法。