CF1876B Effects of Anti Pimples

definieren · 2023-10-09 10:53:18 · 题解

考虑分别计算每个 a_i 对答案的贡献。

可以发现，如果你在 a_i 这个位置染了黑色，所有 i 的倍数的位置都会染上绿色，这部分对最大值的贡献就是 \max_{i \cdot j \le n} a_{i\cdot j}。所以可以对每个 a_i 重新赋值为 \max_{i \cdot j \le n} a_{i \cdot j}。

然后问题就转化为了求 a 的所有子序列的最大值之和。

所以可以对 a 升序排序，然后 a_i 对答案的贡献就是 a_i \times 2^{i - 1}。

时间复杂度 O(n \ln n)。

const int MAXN = 1e5 + 9;
int n, a[MAXN], pw[MAXN];
int ans = 0;

int main() {
    n = Read<int>();
    for (int i = 1; i <= n; i ++) a[i] = Read<int>();
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j += i)
            cmax(a[i], a[j]);
    sort(a + 1, a + n + 1), pw[0] = 1;
    for (int i = 1; i <= n; i ++) pw[i] = add(pw[i - 1], pw[i - 1]);
    for (int i = 1; i <= n; i ++) cadd(ans, int(1ll * a[i] * pw[i - 1] % MOD));
    Write(ans, '\n'); Flush();
    return 0;
}