一个整数的质数分数等于 x 不同质因子的数目。比方说，300 的质数分数为 3 ，因为 300 = 2 * 2 * 3 * 5 * 5
给你一个长度为 n 的正整数数组 nums 和一个整数 k 。
一开始，你的分数为 1 。你可以进行以下操作至多 k 次，目标是使你的分数最大：
选择一个之前没有选过的 非空 子数组 nums[l, ..., r] 。
从 nums[l, ..., r] 里面选择一个质数分数最高的元素 x 。如果多个元素质数分数相同且最高,选择下标最小的一个,将你的分数乘以 x 。
请你返回进行至多 k 次操作后，可以得到的最大分数。
由于答案可能很大，请你将结果对 109 + 7 取余后返回
1. 贡献法 + 单调栈 + 欧拉筛 + 贪心排序 + 快速幂
易知区间的个数有(1+n)*n/2个,首先需要计算区间的主导元素(质数分数最高元素)
由于每个区间计算复杂度也没有必要,这里反过来计算每个元素在多少区间中起作用,结合单调栈使用贡献法
要使得结果最大,优先选择最大的区间进行操作,这里进行贪心排序,优先消耗大的元素的区间
同时,质数分数也可以通过欧拉筛的类似思维,进行预处理,只需计算一次即可
因为涉及到幂运算,同时要取余,这里还要自定义快速幂计算
const int MX = 1e5 + 1;
const int MOD = 1e9 + 7;
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;
}();
long long mypow(long long x,long long n){ //快速幂
if(n==0) return 1;
if(n%2==1) return (mypow(x*x%MOD,n/2)*x)%MOD;
return mypow(x*x%MOD,n/2);
}
class Solution {
public:
int maximumScore(vector<int>& nums, int k) {
//优先取最大,然后次大,每个数有统治辖域,用贡献法中的单调栈实现
int n = nums.size();
vector<int> left(n, -1); //贡献法记录左辖域,开区间
vector<int> right(n, n); //贡献法记录右辖域,开区间
stack<int> st; //单调栈,降序记录
for(int i=0;i<n;i++){//从左往右遍历,记录左侧更大值
while(!st.empty()&&omega[nums[st.top()]] < omega[nums[i]]){//把小于当前数的挤出来,保证对于相同数,前面统辖后面
right[st.top()] = i;
st.pop();
}
if(!st.empty()) left[i] = st.top();//记录左侧更大值
st.push(i);
}
vector<int> id(n);//记录降序下标,优先选更大数
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int i, const int j) {
return nums[i] > nums[j];
});
long long res = 1;
for(int i:id){
long long domain = (i-left[i])*(right[i]-i);// 可以贡献的次数
if(domain>=k){
res = res*mypow(nums[i],k)%MOD;
break;
}
res = res*mypow(nums[i],domain)%MOD;
k-=domain;
}
return res;
}
};