使用模乘逆求字符串的秩(带重复项)

Question

下面的代码用于长度等于或小于12的字符串( int )和长字符串( 20 )。在这段代码中，我使用了公式(N-1)！/ (p1！* p2！* p3！)对于秩的计算，其中p1、p2、p3是重复字符出现的次数。但在输入较大的情况下，阶乘计算的结果不适合于整数(或长)。所以，我不明白我需要修复代码的哪一部分，以及如何修复？我是否需要修正阶乘法，还是需要更改计算等级的公式？据我所知，根据模乘逆，我可以使用公式(A*幂(B，mod-2)% Mod )，其中A是iterativeFactorial(sorts.size())，B是countRepetitions(排序)，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

据我所知，根据模乘逆，我可以使用公式(A*幂(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适合它们！

我不知道你在用第一种方法做什么。您不应该有任何涉及模块操作的部门。使用你提到的功率公式。