class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
}
};
7023. 操作使得分最大
给你一个长度为 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 <= 1051 <= nums[i] <= 1051 <= k <= min(n * (n + 1) / 2, 109)原站题解
golang 解法, 执行用时: 132 ms, 内存消耗: 9.6 MB, 提交时间: 2023-08-14 09:57:03
const mod int = 1e9 + 7
// 预处理 omega
const mx int = 1e5
var omega [mx + 1]int8
func init() {
for i := 2; i <= mx; i++ {
if omega[i] == 0 { // i 是质数
for j := i; j <= mx; j += i {
omega[j]++ // i 是 j 的一个质因子
}
}
}
}
func maximumScore(nums []int, k int) int {
n := len(nums)
left := make([]int, n) // 质数分数 >= omega[nums[i]] 的左侧最近元素下标
right := make([]int, n) // 质数分数 > omega[nums[i]] 的右侧最近元素下标
for i := range right {
right[i] = n
}
st := []int{-1}
for i, v := range nums {
for len(st) > 1 && omega[nums[st[len(st)-1]]] < omega[v] {
right[st[len(st)-1]] = i
st = st[:len(st)-1]
}
left[i] = st[len(st)-1]
st = append(st, i)
}
id := make([]int, n)
for i := range id {
id[i] = i
}
sort.Slice(id, func(i, j int) bool { return nums[id[i]] > nums[id[j]] })
ans := 1
for _, i := range id {
tot := (i - left[i]) * (right[i] - i)
if tot >= k {
ans = ans * pow(nums[i], k) % mod
break
}
ans = ans * pow(nums[i], tot) % mod
k -= tot // 更新剩余操作次数
}
return ans
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
java 解法, 执行用时: 133 ms, 内存消耗: 54.5 MB, 提交时间: 2023-08-14 09:56:45
class Solution {
private static final long MOD = (long) 1e9 + 7;
private static final int MX = (int) 1e5 + 1;
private static final int[] omega = new int[MX];
static {
for (int i = 2; i < MX; i++)
if (omega[i] == 0) // i 是质数
for (int j = i; j < MX; j += i)
omega[j]++; // i 是 j 的一个质因子
}
public int maximumScore(List<Integer> nums, int k) {
var a = nums.stream().mapToInt(i -> i).toArray();
int n = a.length;
var left = new int[n]; // 质数分数 >= omega[nums[i]] 的左侧最近元素下标
var right = new int[n];// 质数分数 > omega[nums[i]] 的右侧最近元素下标
Arrays.fill(right, n);
var st = new ArrayDeque<Integer>();
st.push(-1); // 方便赋值 left
for (int i = 0; i < n; i++) {
while (st.size() > 1 && omega[a[st.peek()]] < omega[a[i]])
right[st.pop()] = i;
left[i] = st.peek();
st.push(i);
}
var ids = new Integer[n];
for (int i = 0; i < n; i++) ids[i] = i;
Arrays.sort(ids, (i, j) -> a[j] - a[i]);
long ans = 1;
for (int i : ids) {
long tot = (long) (i - left[i]) * (right[i] - i);
if (tot >= k) {
ans = ans * pow(a[i], k) % MOD;
break;
}
ans = ans * pow(a[i], (int) tot) % MOD;
k -= tot; // 更新剩余操作次数
}
return (int) ans;
}
private long pow(long x, int n) {
var res = 1L;
for (; n > 0; n /= 2) {
if (n % 2 > 0) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
}
python3 解法, 执行用时: 520 ms, 内存消耗: 41.7 MB, 提交时间: 2023-08-14 09:56:21
# 贡献法+单调栈
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 的一个质因子
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
left = [-1] * n # 质数分数 >= omega[nums[i]] 的左侧最近元素下标
right = [n] * n # 质数分数 > omega[nums[i]] 的右侧最近元素下标
st = []
for i, v in enumerate(nums):
while st and omega[nums[st[-1]]] < omega[v]:
right[st.pop()] = i
if st: left[i] = st[-1]
st.append(i)
ans = 1
for i, v, l, r in sorted(zip(range(n), nums, left, right), key=lambda z: -z[1]):
tot = (i - l) * (r - i)
if tot >= k:
ans = ans * pow(v, k, MOD) % MOD
break
ans = ans * pow(v, tot, MOD) % MOD
k -= tot # 更新剩余操作次数
return ans