题目描述：
给你一个长度为 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\le nums[i] \le 10^5, 1\le n \le 10^5$
题解：
首先要预处理出所有数字的质因子种类数，可以使用线性筛或埃筛。
线性筛质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| vector<bool> notPrime;
vector<int> prime;
vector<int> from;
void sieve(int maxx)
{
notPrime.resize(maxx + 1);
from.resize(maxx + 1);
notPrime[0] = notPrime[1] = true;
for(int i = 2; i <= maxx; ++i)
{
if(notPrime[i])
{
prime.emplace_back(i);
from[i] = i;
}
for(int j = 0; j < prime.size() && i * prime[j] <= maxx; ++j)
{
notPrime[i * prime[j]] = true;
from[i * prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
}
|
加上递推，求质因子个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| vector<bool> notPrime;
vector<int> prime;
vector<int> from;
vector<int> cnt;
void sieve(int maxx)
{
notPrime.resize(maxx + 1);
from.resize(maxx + 1);
notPrime[0] = notPrime[1] = true;
for(int i = 2; i <= maxx; ++i)
{
if(notPrime[i])
{
prime.emplace_back(i);
from[i] = i;
cnt[i] = 1;
}
for(int j = 0; j < prime.size() && i * prime[j] <= maxx; ++j)
{
notPrime[i * prime[j]] = true;
from[i * prime[j]] = prime[j];
cnt[i * prime[j]] = cnt[i] + 1;
if(i % prime[j] == 0) break;
}
}
}
|
思考，如何统计不重复的质因子，比如 $4$ 不同种类的质因子只有一个 $2$ ，重复的不统计进去。例如 $4$ ，当 $i = 2$ 时， $i \times prime[j] = 2 \times 2$ 会筛掉，但是 $cnt[i * prime[j]] = cnt[i] + 1$ 的话就会重复计数这个 $2$ ，所以需要在 $i\neq prime[j]$ 的时候计数。但是例如 $8$ ，在 $i \times prime[j] = 4 \times 2$ 时筛掉，但是 $i\neq prime[j]$ ，会计数 $prime[j]$ ，重复了。需要满足 $from[i] \neq prime[j]$ 才会计数一次。因为每个数只会被最小的质因子筛掉， $i$ 已经被筛过了， $cnt[i]$ 里面是不同种类的质因子个数， $y$ 被最小的质因子 $prime[j]$ 筛掉， $prime[j]$ 要么也是 $i$ 的最小质因子，或者比 $from[i]$ 更小。
反证法：如果 $prime[j]$ 不是 $i$ 的最小质因子，那么 $y = i * prime[j]$ ， $y$ 的最小质因子应该是 $i$ 的最小质因子了，就不是 $prime[j]$ 了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| vector<bool> notPrime;
vector<int> prime;
vector<int> from;
vector<int> cnt;
void sieve(int maxx)
{
notPrime.resize(maxx + 1);
from.resize(maxx + 1);
notPrime[0] = notPrime[1] = true;
for(int i = 2; i <= maxx; ++i)
{
if(notPrime[i])
{
prime.emplace_back(i);
from[i] = i;
cnt[i] = 1;
}
for(int j = 0; j < prime.size() && i * prime[j] <= maxx; ++j)
{
notPrime[i * prime[j]] = true;
from[i * prime[j]] = prime[j];
cnt[i * prime[j]] = cnt[i] + (from[i] != prime[j]);
if(i % prime[j] == 0) break;
}
}
}
|
分解完质因子之后，得到了每个数字的质数分数。考虑每个数字的贡献。如果 $nums[i]$ 是区间中的最高质数分数，那么需要处理出有多少个这样的区间。如果找出右边质数分数比他大的 $right[i]$ ，左侧质数分数大于等于他的 $left[i]$ 。（为什么是小于等于呢？因为相等的选择下标最小的。）
可以使用单调减栈，然后每次遇到一个更大的，更新 $right[i]$ ，弹栈。入栈时更新一下元素的 $left[i]$ ，因为相等的没有弹出去，因此入栈的时候更新 $left[i]$ 刚好就是大于等于他的。
$nums[i]$ 作为最大质数分数的区间个数为 $tot = (i - left[i]) \times (right[i] - i)$ ，贡献为 $nums[i]^{tot}$ 。因为 $tot$ 比较大，所以需要使用快速幂。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
vector<bool> notPrime;
vector<int> prime;
vector<int> from;
vector<int> cnt;
int init = [](int maxx)
{
notPrime.resize(maxx + 1);
notPrime[0] = notPrime[1] = true;
from.resize(maxx + 1);
cnt.resize(maxx + 1);
for (int i = 2; i <= maxx; ++i)
{
if (!notPrime[i])
{
from[i] = i;
prime.emplace_back(i);
cnt[i] = 1;
}
for (int j = 0; j < prime.size() && i * prime[j] <= maxx; ++j)
{
notPrime[i * prime[j]] = true;
from[i * prime[j]] = prime[j];
cnt[i * prime[j]] = cnt[i] + (from[i] != prime[j]);
if (i % prime[j] == 0)
break;
}
}
return 0;
}(1e5);
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const static int mod = 1e9 + 7;
long long qpow(long long a, long long b)
{
long long ret = 1, tmp = a;
while (b)
{
if (b & 1)
ret = ret * tmp % mod;
tmp = tmp * tmp % mod;
b >>= 1;
}
return ret;
}
int maximumScore(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> st(n);
int top = -1;
vector<int> left(n, -1), right(n, n);
for (int i = 0; i < nums.size(); ++i)
{
while (top >= 0 && cnt[nums[st[top]]] < cnt[nums[i]])
{
right[st[top]] = i;
--top;
}
if (top >= 0)
left[i] = st[top];
st[++top] = i;
}
long long ans = 1;
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](const int &x, const int &y)
{ return nums[x] > nums[y]; });
for (auto &x : id)
{
if (k == 0)
break;
long long tot = (right[x] - x) * (x - left[x]);
int times = min(tot, 1ll * k);
ans = ans * qpow(nums[x], times) % mod;
k -= times;
}
return ans;
}
};
|