操作使得分最大

题目

2818. 操作使得分最大

---

给你一个长度为 n 的正整数数组 nums 和一个整数 k 。

一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：

• 选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
• 从 nums[l, ..., r] 里面选择一个 质数分数 最高的元素 x 。如果多个元素质数分数相同且最高，选择下标最小的一个。
• 将你的分数乘以 x 。

nums[l, ..., r] 表示 nums 中起始下标为 l ，结束下标为 r 的子数组，两个端点都包含。

一个整数的 质数分数 等于 x 不同质因子的数目。比方说， 300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5 。

请你返回进行至多 k 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 10^9 + 7 取余后返回。

示例 1：

输入：nums = [8,3,9,3,8], k = 2
输出：81
解释：进行以下操作可以得到分数 81 ：
- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。
81 是可以得到的最高得分。

示例 2：

输入：nums = [19,12,14,6,10,18], k = 3
输出：4788
解释：进行以下操作可以得到分数 4788 ：
- 选择子数组 nums[0, ..., 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。
- 选择子数组 nums[5, ..., 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。
- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为  342 * 14 = 4788 。
4788 是可以得到的最高的分。

提示：

• 1 <= nums.length == n <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= k <= min(n * (n + 1) / 2, 10^9)

题解

方法一：

思路

用埃氏筛，可以预处理出1e5内所有数的不同质因子个数。

现在对于区间中的每个数nums[i]，考虑包含i且选择nums[i]作为分数的区间[l,r]。

如果多个元素质数分数相同且最高，选择下标最小的一个。因此i左侧的值其质数分数应当都小于nums[i]才能保证选择nums[i]作为分数。而i右侧的质数分数可以小于nums[i]也可以等于nums[i].

总之，这样的区间[l,r]满足[i+1, r]区间内的所有值的质数分数小于等于nums[i]的质数分数，所以找到右侧第一个质数分数大于nums[i]的质数分数的位置y；满足[l, i-1]区间内的所有值的质数分数小于nums[i]的质数分数，所以找到左侧侧第一个质数分数大于等于nums[i]的质数分数的位置x。这都可以用单调栈实现，看我单调栈的总结。

显然以nums[i]作为分数的区间有(i-x)*(y-i)个。

由于要在k次操作内选择分数最高，所以我们优先选择num[i]大的值。此外由于分数是累乘的，我们将计算(i-x)*(y-i)个nums[i]的乘积。可以需要用到快速幂。

代码

const int MX = 1e5 + 1;
int omega[MX];
int init = []() {
    for (int i = 2; i < MX; i++)
        if (omega[i] == 0) // i 是质数
            for (int j = i; j < MX; j += i)
                omega[j]++; // i 是 j 的一个质因子
    return 0;
}();
class Solution {
public:
    using ll = long long;
    const int MOD = 1e9+7;
    ll fpow(ll x, ll p) {
        ll rt = 1;
        while (p) {
            if (p&1) rt *= x, rt %= MOD;
            x *= x;
            x %= MOD;
            p >>= 1;
        }
        return rt;
    }

    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> st, lge(n,-1), rg(n,n);
        for (int i=0; i<n; i++) {
            while (st.size() && omega[nums[st.back()]] < omega[nums[i]]) {//非增
                rg[st.back()] = i;
                st.pop_back();
            }
            if (st.size()) lge[i] = st.back();
            st.push_back(i);
        }
        // for (int i:lge) {
        //     cout << i << " ";
        // } cout << endl;
        // for (int i:rg) {
        //     cout << i << " ";
        // } cout << endl;
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return nums[a] > nums[b];
        });
        // for (int i:idx) {
        //     cout << i << " ";
        // } cout << endl;
        ll ans = 1;
        for (int i:idx) {
            ll opt = min(1LL*k, 1LL*(rg[i]-i)*(i-lge[i]));
            ans *= fpow(nums[i], opt);
            ans %= MOD;
            // cout << opt << "opt\n";
            k-=opt;
            if (k == 0) break;
        }
        return ans;
    }
};