康托展开

int cantor(string s){
    int res = 0;
    for(int i = 0;i < s.size();i ++ ){
        int sum = 0;
        for(int j = i + 1;j < n;j ++ )
            if(s[i] > s[j]) sum ++ ;
        res += sum * f[s.size() - i - 1];
    }
    return res;
}

重复的康托展开

typedef long long LL;

const int N = 3010;
const LL mod = 1e9 + 7;

LL f[N], g[N];

class Solution {
public:
    LL qmi(LL a, LL b){
        LL res = 1;
        while(b){
            if(b & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }
    void get_factor(int n){
        f[0] = g[0] = 1;
        for(int i = 1;i <= n;i ++ ){
            f[i] = f[i - 1] * i % mod;
            g[i] = qmi(f[i], mod - 2) % mod;
        }
    }
    int makeStringSorted(string s) {
        int n = s.size(); get_factor(n);
        unordered_map<char, int> cnt;
        for(auto c: s) cnt[c] ++ ;
        LL res = 0;
        for(int i = 0;i < n;i ++ ){
            LL sum = 0;
            for(auto [a, b]: cnt)
                if(a < s[i]) sum += b;
            LL t = sum * f[n - i - 1] % mod;
            for(auto [a, b]: cnt)
                t = t * g[b] % mod;
            res = (res + t) % mod;
            cnt[s[i]] -- ;
        }
        return res % mod;
    }
};