计算重复整数排列的模数

Question

我想计算 P_s mod K 其中 P_s 是集合中元素唯一排列的总数 S。问题是，集合 S 可以有重复，所以 P_s = n! / (f₁!f₂! ... f_n!) ，其中n为元素个数，分母为S中各元素频率阶乘的乘积。

可以假设整数 n 非常大，比如 10^6，并且不太可能适合 uint64_t。甚至可以在不求助于任意精度库的情况下计算 P_s mod K 吗？如果有，有什么快速计算的方法吗？

Answer 1

举个例子9!/(4!3!2!)。这是

9.8.7.6   5.4.3   2.1
------- x ----- x ---
4.3.2.1   3.2.1   2.1

换句话说它是3个二项式系数的乘积9C4 x 5C3 x 2C2。通过这种方式，您总是能够将其简化为二项式系数的乘积。你需要计算这些二项式系数 modulo K 并将答案相乘 modulo K.

所以你需要一种计算二项式系数的有效方法 modulo K.

我不知道这对n == 10^6有多可行，但是这里给出了一种有效计算二项式系数的方法modK：

https://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/

Answer 2

如果你想计算例如n!modK，不需要先计算n!。相反，你可以做一个看起来像这样的循环。

result = 1
for(i = 2; i <= n; i++) {
  result = (result * i) % K
}

解释为什么这有效的最简单方法是查看当您将数字的最后一位与其他数字相乘时会发生什么。例如1234 * 3.结果的最后一位是多少？它是一个 2，等于 (4*3)mod10。结果的最后一位只受两个因素最后一位的影响。在每个数字系统中都是如此。不只是以 10 为基数。因此，变量 result 将结果的最后一位存储在基数 K.

中就足够了

Answer 3

如果需要计算 P_s mod K 对于许多 P_s，那么预先计算 n 可能是明智的！ mod K 对于您可能需要的 n 的所有值（如果 n ≤ 10⁶那就合理了）。

此外，如果 K 是素数，您可以通过乘以要除以的数字的“modular multiplicative inverse”来处理除法。例如，如果 K=1,000,000,007 那么您可以乘以 500,000,004 而不是除以 2。

有几种计算方法，最简单的方法是计算 x^K-2 mod K （这要归功于 Fermat's little theorem）。然后，您也可以预先计算每个阶乘的模乘逆。然后很容易计算 P_s mod K 使用缓存的值。

计算重复整数排列的模数

Calculate modulo of permutations of repeated integers

algorithm

modular-arithmetic