计算nCr模142857的最有效方法

Question

我想计算nCr modulo 142857。以下是我用Java编写的代码：

private static int nCr2(int n, int r) {
    if (n == r || r == 0) {
        return 1;
    }
    double l = 1;
    if (n - r < r) {
        r = n - r;
    }
    for (int i = 0; i < r; i++) {
        l *= (n - i);
        l /= (i + 1);
    }
    return (int) (l % 142857);
}

这给了nCr以O(r)的时间。我想要一个算法在短时间内得到结果。有这样的算法吗？

Answer 1

您可以预先计算给定的n和r对的结果，并在表int t[][]中对它们进行硬编码。

稍后，在运行时，当您需要nCr(n, r)时，只需查找以下表：t[n][r]。

这是运行时的O(1) .

Answer 2

由于您的数字不是素数，所以这个答案不适用。但是，您可以轻松地将142857分解为素数，计算相应的模块，并使用中国剩余定理获得结果。对于您正在使用的数字来说，这可能有意义，也可能没有意义。

在任何情况下，你都必须避免双倍，除非你能确保所有的中间结果都可以精确地用53位来表示(否则你就失去了精度，得到了一个无意义的结果)。

Answer 3

在您提到的函数中，您已经得到了大部分答案。如果n是固定的，并且r是可变的，您可以使用nCr = nC(r-1) *( nCr + 1) /r，所以您可以为nCr使用一个表并逐步构建它(不同于其他答案提到的预计算不是增量的)。

因此，您的新函数可以通过传递一个表进行递归。