题目地址：

https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/description/

给定一个长nnn字符串sss，每次进行这样的操作：找到最大的iii使得s[i−1]>s[i]s[i-1]>s[i]s[i−1]>s[i]，再找到最大的jjj使得∀k∈[i,j],s[i−1]>s[k]\forall k\in[i,j],s[i-1]>s[k]∀k∈[i,j],s[i−1]>s[k]，交换s[i−1],s[j]s[i-1],s[j]s[i−1],s[j]并翻转s[i:]s[i:]s[i:]。问进行多少次操作可以使得sss变为升序。答案模109+710^9+7109+7返回。题目保证sss只含英文小写字母。

这个操作实际上就是求字典序比sss小的最大排列，参考https://blog.csdn.net/qq_46105170/article/details/108543529。那么要求sss进行多少次操作就能升序，即问sss进行多少次操作其字典序会变为最小，即问sss按字典序排名是多少（排名从000开始）。求某个排列的字典序排名可以用康托展开，思路和算法参考https://blog.csdn.net/qq_46105170/article/details/127711927。本题还需要求模109+710^9+7109+7的逆元，可以用费马小定理和快速幂来做，参考https://blog.csdn.net/qq_46105170/article/details/113823892。代码如下：

class Solution {public:vector tr;int n;
#define lowbit(x) (x & -x)void add(int k, int x) {for (; k <= n; k += lowbit(k)) tr[k] += x;}int sum(int k) {int res = 0;for (; k; k -= lowbit(k)) res += tr[k];return res;}int makeStringSorted(string s) {const int P = 1e9 + 7;n = *max_element(s.begin(), s.end()) - 'a' + 1;tr.resize(n + 1);auto fast_pow = [&](long x, int pow = P - 2) {long res = 1;while (pow) {if (pow & 1) res = res % P * x % P;pow >>= 1;x = x % P * x % P;}return res;};long res = 0, fact = 1, mult = 1;int cnt[27];memset(cnt, 0, sizeof cnt);for (int i = s.size() - 1; i >= 0; i--) {int x = s[i] - 'a' + 1;cnt[x]++;mult = mult * fast_pow(cnt[x]) % P;add(x, 1);res = (res + fact * mult % P * sum(x - 1)) % P;fact = (s.size() - i) * fact % P;}return res;}
};

时空复杂度O(n)O(n)O(n)（树状数组上的操作可以视为常数时间，因为树状数组长度不超过272727）。

也可以直接用https://blog.csdn.net/qq_46105170/article/details/127711927里的公式暴力求，代码如下：

class Solution {public:int makeStringSorted(string s) {const int P = 1e9 + 7;int n = s.size();long f[n + 1], g[n + 1];f[0] = g[0] = 1;auto fast_pow = [&](long a, int b) {long res = 1;while (b) {if (b & 1) res = res * a % P;a = a * a % P;b >>= 1;}return res;};for (int i = 1; i <= n; i++) {f[i] = f[i - 1] * i % P;g[i] = fast_pow(f[i], P - 2);}int res = 0, cnt[26], sum = n;memset(cnt, 0, sizeof cnt);auto calc = [&](int sum) {int res = f[sum];for (int i = 0; i < 26; i++) res = (long)res * g[cnt[i]] % P;return res;};for (char ch : s) cnt[ch - 'a']++;for (int k = 0; k < s.size(); k++) {int x = s[k] - 'a';for (int i = 0; i < x; i++) {if (!cnt[i]) continue;cnt[i]--;res = (res + calc(n - 1 - k)) % P;cnt[i]++;}cnt[x]--;}return res;}
};

时空复杂度O(n)O(n)O(n)。