题意
给定一个数组 \([a_1,a_2,a_3.\cdots,a_n]\)，一开始所有元素都为白色。你可以选定其中的至少一个元素涂成黑色，共有 \(2^n - 1\) 种涂法。此时对于所有黑色元素 \(a_i\) , 下标为 \(i\) 的倍数的所有白色元素都将变成绿色。此时数组中所有黑色和绿色元素的最大值记为此种涂法的分数。
问对于所有 \(a^n - 1\) 种涂法，每种涂法的分数之和为多少？
题解
我们考虑涂一个黑色元素 \(a_i\)，记所有下标为 \(i\) 倍数的元素最大值为 \(a_{imax}\)。所有包含涂 \(a_i\) 的方法共有 \(2^{n-1}\) 种。但是这些方案中还可能涂了其他的黑色元素 \(a_j\)，使得 \(a_{jmax} > a_{imax}\)，所以计算 \(a_i\) 的贡献中还要剔除掉这些分数比 \(a_{imax}\) 大的方案数。
所以我们可以反着考虑，计算分数为 \(a_i\) 时的贡献。先将数组从大到小排序。\(a_i\) 作为方案的分数当且仅当 \(i\) 是某个黑色元素的下标倍数，所以我们枚举 \(i\) 的所有因数 \(k\)。如果 \(k\) 之前被更大的 \(a_j\) 枚举过，那么涂 \(a_k\) 的方案的分数肯定是 \(a_j\)，不能记到分数为 \(a_i\) 的贡献里。如果 \(k\) 未被枚举过，那么此时 分数为 \(a_i\) 且涂了 \(a_k\) 的方案 的贡献为 所有包含 \(a_k\) 且不包含枚举过的数的方案数 乘 \(a_i\)（包含枚举过的数的方案，之前记过更大的分数）。
开一个标记数组标记枚举过的因数。将 \(a\) 数组从大到小排序。逐个考虑每一个 \(a_i\) 的所有因数，同时记录此时 \(1\) 至 \(n\) 中还未被标记的数的个数 \(t\)：
-
统计未被标记的因数个数 \(b\)，并标记这些因数。
-
记录 \(a_i\) 的贡献为 \(c_{a_i} = a_i\sum\limits_{j = 1}^{b}2^{t-j}\)，再将 \(t\) 减 \(b\)。
所有包含 \(a_k\) 且不包含枚举过的数的方案数 即为其中的 \(2^{t - j}\)。这是因为此时还未标记的数还有 \(t - j\) 个，而真子集一共有 \(2^{t - j}\) 种。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100010
#define MOD 998244353
#define REP(a, b, i) for(int i = (a); i <= (b); i++)
ll dn[MAXN];
bool vis[MAXN];
int n;
struct Ai{
int ind;
ll num;
}ai[MAXN];
bool cmp(Ai x, Ai y)
{
return x.num > y.num;
}
void calc2n() // 预处理 2 的幂
{
dn[0] = 1;
REP(1, n, i)
dn[i] = ((dn[i - 1] << 1) + MOD) % MOD;
}
ll factor(ll i) //找因数
{
int cnt = 0;
for(ll k = 1; k * k <= i; k++){
if(i % k == 0){
if(!vis[k]) vis[k] = 1, cnt++;
if(!vis[i / k]) vis[i / k] = 1, cnt++;
}
}
return cnt;
}
ll cntsum(ll lf, ll ct) // 计算第 2 步中的求和
{
ll ans = 0;
for(ll i = 1; i <= ct; i++)
ans = (ans + dn[lf - i]) % MOD;
return ans;
}
void work()
{
sort(ai + 1, ai + 1 + n, cmp);
ll lft = n, res = 0; // lft 为尚未标记的数的个数
for(int i = 1; i <= n; i++){
ll k = factor(ai[i].ind);
res = (res + cntsum(lft, k) * ai[i].num % MOD) % MOD;
lft -= k;
}
cout << res;
}
int main()
{
cin >> n;
calc2n();
REP(1, n, i){
ai[i].ind = i;
cin >> ai[i].num;
}
work();
return 0;
}