模乘法逆如何解决大阶乘的溢出

Question

我指的是在InterviewBit上的问题"排序排列秩与重复"，我的解决方案可以产生正确的输出，除了长字符串值。这通常是由于大阶乘的溢出造成的。

我已经通过使用Java中的BigInteger数学类生成了一个解决方案，但是解决方案提示建议使用"模块化乘法逆"作为替代方法来计算(N-1)!/(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

我们可以使用上述属性找到(factorial % 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

再次，要找到没有溢出的模逆，你需要使用模幂。