[第358场周赛]分解质因数+单调栈+快速幂

最近有点水逆，希望厄运赶快退散，一会会去祈福的。

这场周赛依旧是3题遗憾离场，第4题经过提示其实涉及的算法都会但是实在是emmmm过于综合。

7023. 操作使得分最大

提示

困难

10

相关企业

给你一个长度为 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 次操作后，可以得到的 最大分数 。

由于答案可能很大，请你将结果对 109 + 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 <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= min(n * (n + 1) / 2, 109)

Solution

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        # 计算质因数个数
        def cal_pri(n):
            s = set() # 存储所有质因数的哈希表
            x = n
            i = 2
            while i*i <= x:
                while x%i == 0:
                    s.add(i)
                    x //= i
                i += 1
            if x > 1:
                s.add(x)
            return len(s)

        # 快速幂
        def fast_pow(x, e):
            res = 1
            while e:
                if e % 2:
                    res *= x
                    res %= mod
                x = x ** 2 % mod
                e //= 2
            return res

        arr = [cal_pri(num) for num in nums]
        
        # 907.子数组的最小值之和 - 的板子
        # 单调栈
        n = len(arr)
        monoStack = []
        left = [0] * n
        right = [0] * n
        for i, x in enumerate(arr):
            while monoStack and x > arr[monoStack[-1]]:
                monoStack.pop()
            left[i] = i - (monoStack[-1] if monoStack else -1)
            monoStack.append(i)
        monoStack = []
        for i in range(n - 1, -1, -1):
            while monoStack and arr[i] >= arr[monoStack[-1]]:
                monoStack.pop()
            right[i] = (monoStack[-1] if monoStack else n) - i
            monoStack.append(i)
        ans = 1
        
        # 处理个数
        mod = 1000000007
        for x, l, r in sorted(zip(nums, left, right))[::-1]:
            if k >= r * l:
                ans *= fast_pow(x, l * r)
                ans %= mod
                k -= r * l
            else:
                ans *= fast_pow(x, k)
                ans %= mod
                k = 0
            if k == 0:
                break
        return ans

另外对于这种批量质因数可以集中处理：

MOD = 10 ** 9 + 7
MX = 10 ** 5 + 1
omega = [0] * MX
for i in range(2, MX):  # 预处理 omega
    if omega[i] == 0:  # i 是质数
        for j in range(i, MX, i):
            omega[j] += 1  # i 是 j 的一个质因子

作者：灵茶山艾府
链接：https://leetcode.cn/problems/apply-operations-to-maximize-score/solutions/2385936/gong-xian-fa-dan-diao-zhan-pythonjavacgo-23c4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

以上。