我最近想到了以下问题,我很惊讶似乎还没有人问这个问题:
我知道公式其中 是字符串的长度,是每个字符的计数(考虑大小为 的字母表)。因此,字符串 toffee
将具有 不同的排列。
但是当 时,这不再有效了。可以非常大(比如 ),因为计算 会超出 long long int 的范围,并且使用 BigIntegers 会太慢。有没有什么办法可以计算出这个,比如说,或 时间?
如果我预处理来自 的阶乘至 ,我的“字符串”以长度数组的形式出现 其中每个元素包含每个字母的计数,是否可以在 中计算它?或 时间?
对此有任何帮助将不胜感激:)
最佳答案
技巧是注意 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!
和每个计数的阶乘。
这比抵消分数中的因子更容易实现。
关于algorithm - 字符串模素数的不同排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32713762/