帮我编个C++程序 题目描述 给定一个长度为 nn 的序列 aa,我们通过以下方式构造序列 bb: 初始时 b 为空序列。 对于 i=1,2,⋯,n,我们依次向 b的尾部插入1,2,⋯,a[i]。 dXqwq 定义一个序列的最小众数为所有出现次数最大的数的最小值。例如 [1,1,4,5,1,4] 的最小众数为 1,而 [1,14,5,14,19,19,8,10]的最小众数为 14。 你需要求出 b的每个子区间的最小众数的和。由于答案可能很大,你只需要输出它对 998244353 取模后的值。 输入格式 第一行输入一个整数 n。 第二行输入 n 个整数 a[i] 输出格式 输出一个整数,代表 b 的每个子区间的最小众数的和对 998244353取模的值。
时间: 2024-04-18 19:24:47 浏览: 34
下面是一个用 C++ 编写的程序,用于解决上述问题:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> prefixSum(n + 1);
vector<long long> freq(n + 1);
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + a[i - 1];
freq[a[i - 1]]++;
}
long long result = 0;
for (int i = 1; i <= n; i++) {
long long count = 0;
for (int j = 1; j * i <= n; j++) {
count += freq[j * i];
}
result = (result + count * prefixSum[i]) % MOD;
}
cout << result << endl;
return 0;
}
```
这个程序首先读取输入的 n 和序列 a。然后,它使用两个辅助数组 prefixSum 和 freq 来记录前缀和和每个数出现的频率。
接下来,程序通过两层循环计算 b 的每个子区间的最小众数的和。外层循环遍历从 1 到 n 的所有可能的子区间长度,内层循环计算当前子区间长度下的最小众数的个数。最小众数的个数通过遍历每个数的倍数来计算。然后,程序将每个子区间的最小众数的个数乘以该子区间的和,并将结果累加到最终的结果中。
最后,程序将结果对 998244353 取模,并输出。
希望这个程序能满足您的需求!如果有其他问题,请随时提问。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)