leetcode-1830. 使字符串有序的最少操作次数(数位dp+逆元+快速幂+排列)「建议收藏」

全栈程序员-站长 • 2022年8月9日下午4:00 • 未分类 • 阅读 8

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

给你一个字符串 s （下标从 0 开始）。你需要对 s 执行以下操作直到它变为一个有序字符串：

找到最大下标 i ，使得 1 <= i < s.length 且 s[i] < s[i – 1] 。
找到最大下标 j ，使得 i <= j < s.length 且对于所有在闭区间 [i, j] 之间的 k 都有 s[k] < s[i – 1] 。
交换下标为 i – 1 和 j 处的两个字符。
将下标 i 开始的字符串后缀反转。
请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 109 + 7 取余的结果。

示例 1：

输入：s = "cba"
输出：5
解释：模拟过程如下所示：
操作 1：i=2，j=2。交换 s[1] 和 s[2] 得到 s="cab" ，然后反转下标从 2 开始的后缀字符串，得到 s="cab" 。
操作 2：i=1，j=2。交换 s[0] 和 s[2] 得到 s="bac" ，然后反转下标从 1 开始的后缀字符串，得到 s="bca" 。
操作 3：i=2，j=2。交换 s[1] 和 s[2] 得到 s="bac" ，然后反转下标从 2 开始的后缀字符串，得到 s="bac" 。
操作 4：i=1，j=1。交换 s[0] 和 s[1] 得到 s="abc" ，然后反转下标从 1 开始的后缀字符串，得到 s="acb" 。
操作 5：i=2，j=2。交换 s[1] 和 s[2] 得到 s="abc" ，然后反转下标从 2 开始的后缀字符串，得到 s="abc" 。
示例 2：

输入：s = "aabaa"
输出：2
解释：模拟过程如下所示：
操作 1：i=3，j=4。交换 s[2] 和 s[4] 得到 s="aaaab" ，然后反转下标从 3 开始的后缀字符串，得到 s="aaaba" 。
操作 2：i=4，j=4。交换 s[3] 和 s[4] 得到 s="aaaab" ，然后反转下标从 4 开始的后缀字符串，得到 s="aaaab" 。
示例 3：

输入：s = "cdbea"
输出：63
示例 4：

输入：s = "leetcodeleetcodeleetcode"
输出：982157772

提示：

1 <= s.length <= 3000
s 只包含小写英文字母。

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 3010;
int f[N],g[N];

class Solution { 
   
public:
    ll qmi(ll x,int y){ 
   
        ll base = x,res = 1;
        while(y){ 
   
            if(y & 1)res = (res * base) % MOD;
            base = base * base % MOD;
            y >>= 1;
        }
        return res;
    }
    int get(int cnt[]){ 
   
        int ans = 0;
        int sum = 0;
        for(int i = 0;i < 26;i ++)sum += cnt[i];
        ans = f[sum];
        for(int i = 0;i < 26;i ++){ 
   
            ans = ((ll)ans * g[cnt[i]]) % MOD;
        }
        return ans;
    }
    int makeStringSorted(string s) { 
   
        f[0] = g[0] = 1;
        for(int i = 1;i < N;i ++){ 
   
            f[i] = ((ll)f[i - 1] * i) % MOD;
            g[i] = qmi(f[i],MOD - 2);
        }
        int ans = 0;
        int cnt[26] = { 
   0};
        for(auto a : s)cnt[a - 'a'] ++;
        for(auto &a : s){ 
   
            int x = a - 'a';
            for(int i = 0;i < x;i ++){ 
   
                int sum = 0;
                if(cnt[i]){ 
   
                    cnt[i] --;
                    ans = (ans + get(cnt)) % MOD;
                    cnt[i] ++;
                }
            }
            cnt[x] --;
        }
        return ans;
    }
};