CF1876B Tutorial

Aleph_Drawer · 2023-10-10 15:32:45 · 题解

首先，直接按照题目中所描述的方法进行统计的时间复杂度明显难以承受。此时一个比较基础经典却非常有效的技巧是：改变统计方式，改成对于每一个数计算它对答案的贡献。

考虑一个数 a_i 怎样的情况下才能计入贡献。对于一种染色方式，假设 a_i 造成了贡献，显然的，我们要保证大于 a_i 的数的颜色都是白色的，其次，如果有枚举顺序的话，我们要保证先枚举到的等于 a_i 的数的颜色也是白色的。

这启示我们先对 a_i 值排序，并从大到小去枚举。对于 i，不妨记录若 a_i 要造成贡献哪些数不能被染成黑色，这些点显然包括了枚举顺序在它前面的所有的数的位置及其下标的因数位置。假设此类数集合为 S。接下来枚举 i 的因数 j。如果 j 已经被记录不能被染色，就不计入贡献中。否则就计入贡献，假设此类计入贡献的数集合为 T。此时，只要这些数中的任何一个或多个被染色，那么 a_i 就会被染色。

那么 a_i 的贡献明显是 a_i(2^{n - |S|} - 2^{n - |S| - |T|})。答案就是将这些贡献加起来。别忘了每次算完贡献之后要将 T 中的点全部归到 S 中。

时间复杂度是 O(n \log{n}) 的。

我的代码写的比较烂。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e5 + 105, MOD = 998244353;

ll n, a[N], p2[N], cnt, ans;
bool tag[N];
ll rng[N];

bool cmp(ll x, ll y) {
    return a[x] > a[y];
}

int main() {
    scanf("%lld", &n);
    p2[0] = 1;
    for(ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]), p2[i] = p2[i - 1] * 2ll % MOD, rng[i] = i;
    stable_sort(rng + 1, rng + n + 1, cmp);
    ll cnt = 0, tmp = 0; // cnt := |S|, tmp := |T|
    for(ll i = 1; i <= n; i++) {
        ll pos = rng[i];
        if(tag[pos])
            continue;
        for(ll j = 1; j * j <= pos; j++) {
            if(!(pos % j)) {
                if(!tag[j]) {
                    tmp++;
                    tag[j] = 1;
                }
                if(!tag[pos / j]) {
                    tmp++;
                    tag[pos / j] = 1;
                }
            }
        }
        ans += (p2[n - cnt] - p2[n - cnt - tmp]) * a[pos] % MOD;
        cnt += tmp;
        tmp = 0;
        ans %= MOD;
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}