字符串的鮮明排列模素

Question

我最近想到了下面的問題，而且我很驚訝，似乎沒有被任何人誰問這個問題尚未：

給定一個字符串，多少它存在不同的排列，模？

我知道公式其中是串的長度，並是每個字符的計數（考慮大小的字母表）。所以，字符串toffee將有不同的排列。

但這行不通了，當可真大（比如），因爲計算會出去的長的長整型範圍，並使用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!和每個計數值的階乘。

這比取消分數中的因子更容易實施。

Answer 2

串的不同排列組合的數量始終是一個整數，儘管是一個分裂的結果。這是因爲分母的因素基本上「敲除」了分子的一些因素。因此，您可以將該分解作爲後因子運算排除，而不是將您與分母因子匹配的因子的特定因子分開。

一旦你除去了部門，你只剩下模塊化乘法，這很簡單。

Answer 3

如果N不是巨大的（也就是說，它足夠小，可以使用類似Eratosthenes的Sieve篩選），那麼可以使用篩的修改版本計算N!的主要因式分解。

然後，您可以使用素因子計算除法，消除除法兩側存在的因素。

雖然這並沒有考慮到您希望結果以模數爲素數（其中存在更好的解決方案）這一事實，但在一般情況下可能有用。

Answer 4

是的..有解決方案存在。你可以閱讀模塊乘法逆算法。 This

由於模數1000000007（它也是一個主數據）的答案是，您可以嘗試Fermat's little theorem來解決此問題。如果模數爲mod複雜度爲O（N + K * log（mod））。