重复排列：避免溢出

背景：

Given n球使得：

'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...

（当然a + b + c + ... = n)

这些球可以排列的排列数量由下式给出：

perm = n! / (a! b! c! ..)

问题一： 我怎样才能“优雅”地计算perm以避免整数溢出尽可能长，并确保当我完成计算时，我要么有正确的值perm, or I know最终结果会溢出吗？

基本上，我想避免使用 GNU GMP 之类的东西。

可选地，问题 2： 这是一个really坏主意，我应该继续使用 GMP 吗？

这些被称为多项式系数，我将其表示为m(a,b,...).

你可以通过利用这个恒等式来有效地计算它们，避免溢出（这应该很容易证明）：

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

然后使用递归来计算系数就很简单了。请注意，为了避免指数运行时间，您需要缓存结果（以避免重新计算）或使用动态编程。

要检查是否溢出，只需确保总和不会溢出即可。

是的，使用任意精度库来完成这个简单的任务是一个非常糟糕的主意。