D. Effects of Anti Pimples
第一步先把所有的数据进行预处理，将单个位置选为黑色元素时的得分计算出来存入到数组\(b\)中。时间复杂度为\(O(nlog(n))\)。
之后将\(b\)进行排序，然后答案即为\(\sum\limits_{i=1}^{n}b[i]*2^{i-1}\mod 998244353\)
所以总时间复杂度为\(O(nlog(n))\)
代码
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const ll N = 1e5 + 10, mod = 998244353;
int n;
int a[N], b[N];
signed main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for(int i = 1;i <= n;i++)
{
for(int j = i;j <= n;j += i)
{
b[i] = max(b[i], a[j]);
}
}
sort(b + 1, b + n + 1);
ll base = 1;
ll tot = 0;
for(int i = 1;i <= n;i++)
{
tot = (tot + b[i] * base) % mod;
base = base * 2 % mod;
}
cout << tot;
return 0;
}