algorithm - 字符串模素数的不同排列

Question

我最近想到了以下问题，我很惊讶似乎还没有人问这个问题:

给定一个字符串，它存在多少种不同的排列，取模 ？

我知道公式其中 是字符串的长度，是每个字符的计数(考虑大小为 的字母表)。因此，字符串 toffee 将具有 不同的排列。

但是当 时，这不再有效了。可以非常大(比如 )，因为计算 会超出 long long int 的范围，并且使用 BigIntegers 会太慢。有没有什么办法可以计算出这个，比如说，或 时间？

如果我预处理来自 的阶乘至 ，我的“字符串”以长度数组的形式出现 其中每个元素包含每个字母的计数，是否可以在 中计算它？或 时间？

对此有任何帮助将不胜感激:)

Answer 1

技巧是注意 p = 10^9 + 7 是质数。因此，我们可以使用乘法逆元和Fermat's little theorem。将公式中的除法转换为逆的乘法:

n! / (a1!*...*ak!) = 

n! * a1!^(p - 2) * ... * ak!^(p - 2) (mod p)

这将是您的公式 mod p，没有除法且易于实现(只需使用模块化 exponentiation by squaring )。

复杂度将为 O(k log p + n)，因为我们有 O(k) 次乘法，对于每个乘法，O(log p) 求幂，我们还必须计算 n! 和每个计数的阶乘。

这比抵消分数中的因子更容易实现。