计算重复整数的置换模

Question

我想计算P _s mod K，其中P _s是集合S中元素的唯一排列的总数。问题是，集合S可以有重复，所以P _s = n！/（f ₁！f ₂！... f _n！），其中n是元素的数量，分母是S中每个元素的频率阶乘的乘积。

可以假设整数n很大，例如，大约10^6不大可能适合a 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。这样，您将始终能够将其减少为二项式系数的乘积。您需要对这些二项式系数取模，K然后将答案乘以模K。

因此，您需要一种有效的方法来计算模的二项式系数K。

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