当阶乘数在n的范围内时，如何有效地计算它们？

Question

任务:给定两个长度为n的数组a，b为对称，排列为1，.，n，计算数组c=[ a!/b！，.，an-1!/bn-1！]在O(n)时间内(因此，除以给定索引处a和b中值的阶乘。)

我似乎想不出一个解决办法。在我看来，最接近解决方案的想法可能是将数组从高到低排序，距离ai和bi很远。然后保存第一个a!/b的结果！当你前进到较低的差异时，只需要稍微缩小一点。但这并不说明(ai，bi)和(aj，bj)之间的间隔可能只是不重叠。

现在，我不知道这是否只是一个错误的要求，虽然一个人是无限的空间。

Answer 1

您可以创建第四个数组，以便d[i] <- i * d[i-1] by Theta(n) (请注意，d[1] <- 1)。现在，通过a和b，计算c，如下所示：

for i <- 1 to n
    c[i] <-  d[a[i]]/d[b[i]]

在上面，数组是一个基于一个的索引.