algorithm - 计算排列 P(n,r) 的最有效方法，其中 n 可以是一个大整数

Question

如果 n 可以大到 1M 而 r 大约 100，那么计算 nPr 的最有效方法是什么。

Answer 1

P(n,r) = n! / (n-r)!

我们可以轻松删除 (n-r)!从提名人和分母。现在公式是

P(n,r) = n*(n-1)*..(n-r+1)

.

.

.

旧答案，不是针对这个问题，关于组合:

C(n,k) = n! / (k! * (n-k)!)

我们可以轻松删除 (n-k)!从提名人和分母。现在公式是

C(n,k) = n*(n-1)*..(n-k+1) / k! = n*(n-1)*..(n-k+1) / (1 * 2 * ...*k)

如果我们先算全提名人，会很大。

但我们可以交替执行步骤 - 取 n，然后除以分母的第一项 (1)，乘以 (n-1) - 除以分母的第二项 (2)，依此类推。

 C(n,k) = n / 1 * (n-1) / 2 * (n-2) / 3 .. * (n-k+1) / k

请注意，部分提名产品总是可以被相同长度的部分分母产品整除。

使用这种方法，中间结果不是很大，大数(长算术)的计算会更快。