一个以模数为模的字符串的不同排列
我最近想到了以下问题,我很惊讶似乎没有人问过这个问题:
给定一个字符串,存在多少个不同的排列,以模为单位 
？
我知道这个公式 
哪里 
是字符串的长度,和 
是每个角色的数量(考虑大小的字母表 
).所以,字符串toffee会有
不同的排列.
但是这不再适用了 可能真的很大(比如说 
),自计算 
会超出long long int的范围,使用BigIntegers会太慢.有没有办法计算这个,比方说,
要么 
时间？
如果我预处理了因子 
至 ,我的"字符串"以长度数组的形式出现 其中每个元素包含每个字母的计数,是否可以计算它 
要么 
时间？
将不胜感激任何帮助:)
诀窍是要注意这p = 10^9 + 7是一个素数.因此,我们可以使用乘法逆和费马小定理将公式中的除法转换为乘法的乘法:
n! / (a1!*...*ak!) =
n! * a1!^(p - 2) * ... * ak!^(p - 2) (mod p)
这将是您的公式mod p,没有分区和简单的实现(只需通过平方使用模幂运算).
复杂性将是O(k log p + n),因为我们有O(k)乘法,并且对于每一个,都是O(log p)取幂,我们还必须计算n!每个计数的因子.
这比取消分数中的因子更容易实现.