模块乘法逆解决大型因子溢出的问题？

我在InterviewBit中提到了“Sorted Permutation Rank with Repeats”这个问题，我的解决方案可能会产生除长字符串值之外的正确输出。这通常是由大型因子溢出引起的。模块乘法逆解决大型因子溢出的问题？

我已经使用Java的BigInteger数学类制作了解决方法，但解决方案提示建议使用“Modular Multiplicative Inverse”作为替代方法来替代计算（N-1）！ /（p1！* p2！* p3！...）其中p1，p2和p3是字符串中重复字符的频率。

所以我的问题是，“Modular Multiplicative Inverse”如何帮助解决不适合整数基元类型的大因子值，以及它背后的数学直觉是什么？我知道如何解决这个编程问题，但阻止成功提交的唯一部分是长字符串值。

非常感谢任何解释！我的解决方案在下面生成，而不使用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; 
    } 
}

来源

2016-10-01 Qin Zhengquan

你错过这里的一个关键特性是，

(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。

来源

2016-10-01 05:19:33

模块乘法逆解决大型因子溢出的问题？

回答

相关问题