(组合数，逆元)1830. 使字符串有序的最少操作次数

1830. 使字符串有序的最少操作次数

能看出来这是下一个排列的操作的逆运算（上一个操作）也需要经验。。能看出来这一点，实际上求的就是这个排列是第几个排列。

坑神的题解，但是这个已经tle了，数据规模是3500，因为求组合数的复杂度是n^2。需要用乘法逆元计算。

逆元就是

const int N = 3010;
typedef long long ll;
class Solution {
 public:
  const int MOD = 1e9 + 7;
  ll fact[N], infact[N];
  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 init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++) {
      fact[i] = fact[i - 1] * i % MOD;
      infact[i] = infact[i - 1] * qmi(i, MOD - 2) % MOD;
    }
  }
  int makeStringSorted(string s) {
    init();
    int n = s.size();
    int cnt[300];
    memset(cnt, 0, sizeof cnt);
    ll res = 0;
    for (int i = n - 1; i >= 0; i--) {
      cnt[s[i]]++;
      for (int j = 'a'; j < s[i]; j++) {
        if (!cnt[j]) continue;
        int len = n - i - 1;
        cnt[j]--;
        ll cur = fact[len];
        for (int k = 'a'; k <= 'z'; k++) {
          cur = (cur * infact[cnt[k]]) % MOD;
        }
        cnt[j]++;
        res = (res + cur) % MOD;
      }
    }
    return res;
  }
};