Distinct permutations of a string modulo a prime

Question

I thought of the following problem recently, and I'm quite surprised that there doesn't seem to be anybody who asked this question yet:

Given a string, how many distinct permutations of it exist, modulo ?

I know the formula where is the length of the string, and are the count of each character (considering an alphabet of size ). So, the string toffee would have different permutations.

But this doesn't quite work anymore when can be really large (say ), since computing would go out of the range of long long int, and using BigIntegers would be too slow. Is there any way to compute this in, say, or time?

If I preprocessed the factorials from to , and my "strings" came in the form of an array of length where each element contained the count of each letter, would it be possible to compute it in or time?

Would appreciate any help on this :)

Answer 1

The trick is to note that p = 10^9 + 7 is a prime number. Therefore, we can use multiplicative inverses and Fermat's little theorem to turn the divisions in your formula into multiplications by the inverses:

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

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

Which will be your formula mod p with no divisions and an easy implementation (just use modular exponentiation by squaring).

Complexity will be O(k log p + n), since we have O(k) multiplications, and for each one, an O(log p) exponentiation, and we must also compute n! and the factorial of each count.

This is easier to implement than cancelling out factors in the fraction.