使用模乘逆查找字符串的秩（有重复项）

Question

对于长度等于或小于 12（如果是 int）和 20（如果是 long）的字符串，此代码可以很好地工作。在这段代码中我使用了公式（N-1）！ / (p1! * p2! * p3! ... ) 用于计算排名，其中 p1、p2、p3 是重复字符出现的次数。但是在大输入的情况下，阶乘计算的结果不适合整数（或长整数）。所以，我不明白我需要修复代码的哪一部分以及如何修复？我需要修复阶乘法还是需要更改排名计算公式？据我所知，根据模乘逆我可以使用公式 (A*power(B,Mod-2))%Mod，其中 A 是 iterativeFactorial(sorts.size()) ,B 是 countRepetitions(sorts)，Mod 是 1000003。但是如果我用这个公式代替 (N-1)！ / (p1! * p2! * p3! ... ) 我的结果不正确。因此，我将非常感谢您澄清使用模乘逆计算排名以及我可以修复我的代码以处理大输入的方式。

示例："adfadfcvcvbgfgrewfdfdsfgfgfhfhcxxse" 的排名必须是 874647，但现在我得到了 511521

public static int myFindRank(String A){
        int rank = 0;
        String sortedAndUnique = "";
        int temp;
        Set<Character> uniques = new TreeSet<Character>();
        List<Character> sorts = new ArrayList<Character>();

        for (int i = 0; i<=A.length()-1; i++){
            char x = A.charAt(i);
            uniques.add(x);
        }

        for (int i = 0; i<=A.length()-1; i++){
            char x = A.charAt(i);
            sorts.add(x);
        }

        for (Character c : uniques) {
            sortedAndUnique = sortedAndUnique + c;
        }

        for (int i = 0; i<A.length()-1; i++){
            for (int j = 0; j<A.length(); j++){

                if (A.charAt(i) == sortedAndUnique.charAt(j)) {
                    Character c = A.charAt(i);
                    sorts.remove(c);
                    i++;
                    temp = 0;

                    while (sortedAndUnique.charAt(temp) != A.charAt(i)) {
                        Character x = sortedAndUnique.charAt(temp);
                        temp++;
                        if (sorts.contains(x)) {
                            sorts.remove(x);
                            rank = rank + iterativeFactorial(sorts.size())/ countRepetitions(sorts);
                            sorts.add(x);
                        }
                    }

                    if (sortedAndUnique.charAt(temp) == A.charAt(i)) {
                        Character y = A.charAt(i);
                        sorts.remove(y);
                    }
                    break;
                } else {
                    Character c = sortedAndUnique.charAt(j);
                    if (sorts.contains(c))  {
                        sorts.remove(c);
                        rank = rank + iterativeFactorial(sorts.size())/ countRepetitions(sorts);
                        sorts.add(c);
                    }
                }
            }
        }

        return (rank+1)%1000003;
    }


public static int countRepetitions(List A){

        int repetitions = 1;

        List<Character> chars = new ArrayList<Character>();
        Set<Character> unique = new TreeSet<Character>();

        for (int i = 0; i<=A.size()-1; i++){
            Character x = (Character) A.get(i);
            chars.add(x);
            unique.add(x);

        }

        for (Character c : unique) {
            repetitions = repetitions * iterativeFactorial(Collections.frequency(chars, c));

        }
        return repetitions;

    }


public static int iterativeFactorial(int number) {

        if (number == 0)
            return 1;

        int i;
        for(i=number; number>1; i=i*number) {
            number--;

        }
        return i;
    }

自定义电源方法：

 public static int callPow(int num)

    {

        int ans = 1, base = num;

        int power = 1000003 - 2;

        while (power > 0) {

            if (power == 1) {

                return (ans * base) % 1000003;

            }

            if (power % 2 == 0) {

                base = (base * base) % 1000003;

                power /= 2;

            } else {

                ans = (ans * base) % 1000003;

                power--;

            }

        }

        return ans;

    }

Answer 1

As far as i know according to modular multiplicative inverse i can use formula (A*power(B,Mod-2))%Mod,

虽然在数学上是正确的，但这可能会溢出。您需要在每个步骤中使用模数：

[(A % Mod) * (power(B, Mod - 2) % Mod)] % Mod

所以在你的代码中：

    for(i=number; number>1; i=i*number) {

更改为：

    for(i=number; number>1; i=(i*number) % Mod) {

repetitions = repetitions * iterativeFactorial(Collections.frequency(chars, c));

更改为：

repetitions = (repetitions * iterativeFactorial(Collections.frequency(chars, c))) % Mod;

注意： 您应该使用 Mod*Mod 适合的数据类型！

而且我不确定您在第一种方法中做了什么。您不应该有任何涉及模运算的部门。使用您提到的幂公式。

使用模乘逆查找字符串的秩（有重复项）

Find the rank of the string (with duplicates) using modular multiplicative inverse

java

algorithm

rank