模块乘法逆如何解决大因子的溢出?

我在InterviewBit上提到了“使用重复排序排列等级”的问题,除了长字符串值,我的解决方案可以产生正确的输出 . 这通常是由大因子的溢出引起的 .

我已经通过使用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;
  }
}

回答(1)

2 years ago

您在这里缺少的一个关键属性是,

( 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

再次找到没有溢出的模块化逆,您将需要使用模幂运算 . 你可以阅读它here .