[InterviewBit] Sorted Permutation Rank with Repeats

Sorted Permutation Rank with Repeats

  • Time : O(|A|log(mod))
  • Space : O(|A|)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long long modpow(long long n, long long x, long long mod) {
if(x == 0) return 1;
long long res = modpow(n,x>>1,mod);
res = (res * res) % mod;
if(x & 1) res = (res * n) % mod;
return res;
}

int Solution::findRank(string A) {
vector<long long> freq(300);
vector<long long> fact {1};
long long mod = 1000003;
for(int i = 0; i < A.length(); i++) {
freq[A[i]]++;
fact.push_back(fact.back() * (i + 1) % mod);
}

long long res = 1;
for(int i = 0; i < A.length(); i++) {
long long cnt = 0, d = 1;
for(int j = 0; j < A[i]; j++) cnt += freq[j];
for(int j = 0; j < 300; j++) d = d * fact[freq[j]] % mod;
long long p = modpow(d,mod - 2,mod);
res = (res + cnt * fact[A.length() - i - 1] % mod * p % mod) % mod;
freq[A[i]]--;
}
return res;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/05/PS/interviewbit/sorted-permutation-rank-with-repeats/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.