モジュラ乗法逆解法は、大きなファクタリゼーションに対してどのようにオーバーフローしますか？

Question

私はInterviewBitの "並べ替え順並べ替え順位"を参照していましたが、私の解決策は長い文字列値を除いて正しい出力を生成することができました。これは、通常、大階乗のオーバーフローによって発生します。

私はJavaのBigInteger数学クラスを使用して回避策を作成しましたが、（N-1）を計算する代わりに回避策として「Modular Multiplicative Inverse」を使用することをおすすめします。 /（p1！* p2！* p3！...）ここで、p1、p2、p3は文字列中の重複文字の頻度です。

私の質問は、「モジュラ乗法逆数」は、整数プリミティブ型に適合しない大きな階乗値をどのように解決し、その背後にある数学的直感は何ですか？私はこのプログラミングの問題を解決する方法を知っていますが、提出が成功するのを防ぐ唯一の部分は長い文字列の値です。

大変感謝しております。私の解決策はBigIntegerクラスを使わずに、以下のように作成されます。

public class Solution { 

    public long fact(int n) { 
     return (n <= 1) ? 1 : (n * fact(n-1)); 
    } 

    public HashMap<Character, Integer> generateFreq(ArrayList<Character> charList){ 
     HashMap<Character, Integer> map = new HashMap<Character, Integer>(); 
     for (int i = 0; i < charList.size(); i++){ 
      char c = charList.get(i);  
      if (!map.containsKey(c)) map.put(c, 1); 
      else map.put(c, map.get(c)+1); 
     } 
     return map; 
    } 

    public int findRank(String a) { 
    char[] charArray = a.toCharArray(); 
    ArrayList<Character> charList = new ArrayList<Character>(charArray.length); 
    ArrayList<Character> sortedCharList = new ArrayList<Character>(charArray.length); 
    for (char c : charArray){ 
     charList.add(c); 
     sortedCharList.add(c); 
    } 

    Collections.sort(sortedCharList); 

    long rank = 1; 
    int factNum = charArray.length - 1; 
    int matchedIndex = 0; 
    int index = 0; 
    while (!sortedCharList.isEmpty()){ 
     char currChar = sortedCharList.get(index); 
     if (currChar != charList.get(matchedIndex)){ 
       HashMap<Character, Integer> mapFreq = generateFreq(sortedCharList); 
       if (mapFreq.get(currChar) > 1){ 
        mapFreq.put(currChar, mapFreq.get(currChar)-1); 
       } 
       long denom = 1; 
       for (char c : mapFreq.keySet()){ 
        denom *= fact(mapFreq.get(c)); 
       } 
       long factVal = fact(factNum); // prob: factVal overflows 
       rank += factVal/denom; 
       while (index < sortedCharList.size()){ 
        if (sortedCharList.get(index) != currChar)break; 
        index++; 
       } 
      } 
     else { 
       sortedCharList.remove(index); 
       index = 0; 
       factNum--; 
       matchedIndex++; 
     } 
    } 
    return (int) rank %1000003; 
    } 
} 

Answer 1

あなたがここに欠けている重要な特性は、

(A * B) % MOD = (A % MOD * B % MOD) % MOD 

が

我々は見つけることができる、ということである（階乗％MOD）彼らはので、MOD値とドンの上に行かないように、上記のプロパティを使用して、整数の上限を超えています。

fact[1]=1; 
for(int i=2;i<=n;i++) 
    fact[i]= ((fact[i-1] % MOD) * (i % MOD)) % MOD; 

したがって、（N-1）！ /（P1！* P2！* P3！...）

ans = fact[N-1] 
for(i = 1 ; i <= number_of_pi ; i++) 
    ans = (ans % MOD * modular_inverse(fact[p[i]]) % MOD) % MOD; 
// here p[1] = p1, p[2] = p2 and so on 

モジュラ逆数は、あなたがべき乗剰余演算を使用する必要がありますがオーバーフローすることなく、モジュラー逆を見つけること

再び

(1/A) % MOD = A^(MOD - 2) % MOD 

、で与えられます。あなたはそれについてhereを読むことができます。