Сортировка ранга перестановки с повторениями: переполнение - PullRequest
Новая
       30

Сортировка ранга перестановки с повторениями: переполнение

0 голосов
/ 20 апреля 2020

ПРОБЛЕМА :

По заданной строке найдите ранг строки среди ее перестановок, отсортированных по лексикографическому признаку. Обратите внимание, что символы могут повторяться. Если символы повторяются, нам нужно посмотреть на ранг в уникальных перестановках.

The answer might not fit in an integer, so return your answer % 1000003

Я пытался решить эту проблему с помощью C ++, я написал следующий код: 

// https://www.youtube.com/watch?v=-MpL0X3AHAs


long long mod = 1000003;
int Solution::findRank(string A) {
    vector<vector<int>> rep(A.size());
    vector<int> ranklessthan(A.size());
    int n = A.size();
    long long fact[n+1];
    fact[0] = 1;
    for (long long i = 1; i <= n; ++i)
    {
        fact[i] = (i%mod)*(fact[i-1]%mod)%mod;
    }

    //To store number of characters less than current index character after it.
    for(int i=A.size()-1;i>=0;i--){
        int rankless = 0;
        for (int j = i+1; j < A.size(); ++j)
        {       
            if (A[j]<A[i])
            {
                rankless++;

            }
        }
        ranklessthan[i] = rankless;
    }

//To store the number of repetitions after an index i(including A[i])
    unordered_map<char, int> m1;
    for(int i=A.size()-1;i>=0;i--){
        int reps = 1;
        m1[A[i]]++;

        for(auto j=m1.begin();j!=m1.end();j++){
            rep[i].push_back(j->second);
        }
    }


    long long ans = 0;
    for (int i = 0; i < n; ++i)
    {
        long long num = ranklessthan[i];

        num= ((num%mod)*(fact[n-i-1]%mod))%mod;

        num = num%mod;
        //cout<<" num: "<<num<<endl;
        long long divide = 1;
        for (int j = 0; j < rep[i].size(); ++j)
        {
            divide = (divide%mod)*((fact[rep[i][j]])%mod);
            divide = divide%mod;

        }
        num = num/divide;

        // cout<<num<<" ";
        ans+=num;

        ans = ans%mod;
    }

    return (int)((ans+1)%1000003);
}

Я использовал все go, объясненное здесь:

https://www.careerbless.com/calculators/rank/index.php

https://www.youtube.com/watch?v=-MpL0X3AHAs

Код отлично работает для небольших строк, но не работает для больших строк, таких как sadasdsasassasas. Это дает мне 100, тогда как ответ должен быть 208526. Это прекрасно работает, если я удаляю мод , но это, в свою очередь, приводит к другим результатам go неправильно.

Я потратил на это часы, но все еще не мог понять. Пожалуйста, помогите мне отладить это. Ошибка в ответе наиболее вероятна из-за переполнения.

...