Moe's CF Life

喵哈喽~！各位初次见面或者好久不见的Master们，咱是乃爱的猫娘解说员的说！今天我们要一起解决的是一道有点绕，但想通了就非常有趣的题目哦！准备好和咱一起开动脑筋了吗？喵~

B. Effects of Anti Pimples

题目大意

Chaneka酱有一个长度为 n 的数组 a，一开始所有元素都是白色的。

她会玩一个染色游戏，规则是这样的喵：

首先，她会选择一个或多个不同的下标，把这些位置的元素涂成黑色。
然后，对于所有是黑色元素下标倍数的白色元素，她会把它们涂成绿色。
一次游戏结束后，她的得分是所有黑色和绿色元素中，a[i] 值的最大值。

现在的问题是，总共有 2^n - 1 种选择黑色下标的方案（因为至少要选一个嘛）。我们需要计算出所有这些方案的得分总和，最后结果对 998244353 取模。

是不是听起来有点复杂？别怕别怕，跟着咱的思路走，很快就能明白啦，喵~

题解方法

首先呀，咱肯定不能真的去一个一个地枚举所有 2^n - 1 种情况。n 最大有 10^5 呢，这要是直接算，咱的电脑就要冒烟啦，喵呜~

所以，咱得换个思路！这种求“所有情况的最大值之和”的问题，有一个经典的思考方式，就是把“求和”变成“计数”的说。

一个方案的得分是 S，那么它就会在 score >= 1, score >= 2, ..., score >= S 的时候被各计算一次，总共被算了 S 次。所以，我们可以得到这样一个神奇的等式：

所有方案的分数总和 = Σ (v=1 to max_a) (得分至少是 v 的方案数)

这里的 max_a 指的是数组 a 中元素的最大值。

是不是很神奇的喵？这样一来，我们就把问题转化成了：对于每个可能的得分值 v，有多少种选择黑色下标的方案，能让最终得分大于等于 v？

直接计算“大于等于v”的方案数还是有点麻烦，不如我们算它的反面：“得分小于v”的方案数，然后用总方案数减掉它！

一个方案的得分要小于 v，意味着所有被染成黑色或者绿色的元素，它们在数组 a 里的值都要小于 v，对吧？

为了方便判断，我们先预处理一个数组 M。M[i] 表示所有下标是 i 的倍数的位置上 (a[i], a[2i], a[3i], ...)，a 值的最大值。

这样一来，如果我们选择了一个下标 i 涂成黑色，那么所有 i 的倍数都会被波及。为了保证最终得分小于 v，就必须保证这些被波及的位置上的 a 值都小于 v，也就是说，M[i] 本身要小于 v。

所以，一个方案的得分小于 v，当且仅当，我们选择的所有黑色下标 i 都满足 M[i] < v。

好啦，思路清晰了！

我们先找出所有满足 M[i] < v 的下标 i。
假设这样的下标总共有 m_v 个。
那么“得分小于v”的方案数，就是从这 m_v 个下标里选出任意非空子集的数量，也就是 2^(m_v) - 1 种。
总的非空方案数是 2^n - 1。
所以，得分大于等于 v 的方案数就是：(2^n - 1) - (2^(m_v) - 1) = 2^n - 2^(m_v)。

问题解决啦，喵~！我们只需要对 v 从 1 到 max_a 遍历，累加 2^n - 2^(m_v) 就可以得到最终答案了。

题解

好啦，思路理清了，接下来就是动手写代码啦~！让咱一步一步来~

第一步：预处理 M 数组喵~

我们需要计算出每个 M[i] = max(a[j]) 其中 j 是 i 的倍数。这可以用一个双重循环搞定。外层循环 i 从 1 到 n，内层循环 j 从 i 开始，每次增加 i，直到 n。

cpp

// M[i] 存储所有下标是 i 的倍数的位置上，a 值的最大值
std::vector<int> M(n + 1, 0);
for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; j += i) {
        M[i] = std::max(M[i], a[j]);
    }
}

这个循环的时间复杂度不是 O(n^2) 而是 O(n log n) 的哦，因为内层循环的执行次数是 n/1 + n/2 + ... + n/n，这是一个调和级数，喵~

第二步：统计 M[i] 的分布情况喵~

我们想知道对于每个 v，有多少个 i 满足 M[i] < v。为了快速查询，我们可以先用一个 count 数组统计每个值 v 出现了多少次（即有多少个 i 使得 M[i] = v），然后再做一个前缀和。

prefix_count[v] 存储满足 M[i] <= v 的 i 的数量。那么我们需要的 m_v（即满足 M[i] < v 的 i 的数量）就等于 prefix_count[v-1]。

cpp

// count[v] 存储 M[i] == v 的 i 的数量
std::vector<long long> count(max_a + 2, 0);
for (int i = 1; i <= n; ++i) {
    count[M[i]]++;
}

// prefix_count[v] 存储 M[i] <= v 的 i 的数量
std::vector<long long> prefix_count(max_a + 2, 0);
for (int v = 1; v <= max_a + 1; ++v) {
    prefix_count[v] = prefix_count[v - 1] + count[v];
}

第三步：预处理2的幂次喵~

因为要多次用到 2^k，所以我们提前把它们都算好存起来，避免重复计算。记得每一步都要取模哦！

cpp

std::vector<long long> p2(n + 1);
p2[0] = 1;
for (int i = 1; i <= n; ++i) {
    p2[i] = (p2[i - 1] * 2) % MOD;
}

第四步：计算最终答案喵~

万事俱备，只欠东风！我们循环 v 从 1 到 max_a，累加我们推导出的公式 2^n - 2^(m_v)。

cpp

long long total_sum = 0;
long long p2_n = p2[n];

for (int v = 1; v <= max_a; ++v) {
    // m_v 是 M[i] < v 的 i 的数量，也就是 M[i] <= v-1 的数量
    long long m_v = prefix_count[v - 1];
    
    // 得分 >= v 的方案数 = 2^n - 2^(m_v)
    long long count_ge_v = (p2_n - p2[m_v] + MOD) % MOD;
    
    // 累加到总和里
    total_sum = (total_sum + count_ge_v) % MOD;
}

std::cout << total_sum << std::endl;

注意减法取模的时候要 (a - b + MOD) % MOD，防止结果变成负数，这是个好习惯的说！

知识点介绍

这道题虽然看起来是道数学题，但其实用到了很多算法竞赛里的小技巧呢，喵~

贡献法 (Contribution Technique) 最核心的就是这个啦！把求“最大值/最小值之和”这类问题，转化为对每个值 v 计算“有多少个方案的结果大于等于/小于等于 v”。这是个超级有用的思想，Master一定要记住哦！
调和级数复杂度 (Harmonic Series Complexity) 咱在计算 M 数组时用的那个双重循环，for i... for j=i...，它的时间复杂度不是 O(n^2) 而是 O(n log n)。很多和约数、倍数相关的题目都会遇到它！
前缀和 (Prefix Sum) 用来快速查询“小于或等于某个值”的元素数量，是个基础但非常实用的技巧，喵。
模运算 (Modular Arithmetic) 老朋友了~处理大数问题必不可少，记得加法、乘法要取模，减法要 (a - b + MOD) % MOD 防止出现负数哦！

好啦，今天的题解就到这里啦！Master有没有觉得豁然开朗呢？只要转换一下思路，难题也能变得很可爱！下次再见啦，喵~！

B. Effects of Anti Pimples ​

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

B. Effects of Anti Pimples

题目大意

题解方法

题解

知识点介绍