Moe's CF Life

Appearance

D. Winter is here - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 428 (Div. 2) 标签: combinatorics, dp, math, number theory 难度: *2200

喵喵，我们要做什么呀？ ​

Nya好，各位Master！今天我们要帮助北境的雪诺哥哥计算他军队的总战斗力，为抵御异鬼做准备，喵~

事情是这样的： 雪诺哥哥有 n 个士兵，每个士兵都有一个力量值 a_i。 他定义了一个叫做“氏族” (clan) 的东西：

  • 一个氏族就是一群士兵的集合（下标要递增哦）。
  • 关键是，这个氏族里所有士兵力量值的最大公约数 (GCD) 必须 大于1。

一个氏族的战斗力被定义为： 氏族的人数 k 乘以 他们的GCD。

我们的任务就是，找出所有可能的氏族，把它们的战斗力全部加起来，得到一个总和。因为这个数字可能会非常大，所以结果要对 10^9 + 7 取模，的说！

举个例子：如果士兵力量是 [3, 3, 1]，那氏族有 {第1个士兵} (GCD=3), {第2个士兵} (GCD=3), {第1、2个士兵} (GCD=3)。 总战斗力就是 (1 * 3) + (1 * 3) + (2 * 3) = 3 + 3 + 6 = 12 啦~

来和咱一起分析吧，喵~ ​

直接去枚举所有可能的氏族（子集）实在是太慢啦，2^n 的复杂度会让电脑酱罢工的！所以我们必须换个聪明的思路，喵~

不直接看“氏族”，我们换个角度，从GCD的值入手！

最终的答案是 Σ (k * gcd)，我们可以把它改写成 Σ_{g=2 to max_A} g * (所有GCD恰好为g的氏族的人数之和)。

这样一来，问题就变成了：对于每一个 g > 1，我们如何求出“所有GCD恰好为g的氏族的人数之和”呢？ 我们把这个值记作 T(g)。那么最终答案就是 Σ_{g=2 to max_A} g * T(g)。

容斥原理登场！ ​

“恰好”等于 g 这个条件太严格了，不好算呀。数学里有个经典套路，就是先把条件放宽，再把多余的部分减掉。这就是容斥原理！

我们不直接求 T(g)，而是先求一个更容易计算的东西：S(g)。 S(g) 表示 “所有GCD是g的倍数”的氏族的人数之和。

这个 S(g) 怎么求呢？

  1. 首先，我们筛选出所有力量值是 g 的倍数的士兵。假设有 c_g 个。
  2. 任何由这 c_g 个士兵组成的非空氏族，它们的GCD必然是 g 的倍数。
  3. 现在问题就变成了：从 c_g 个士兵中，选出任意数量的人（至少一人）组成氏族，所有这些氏族的人数总和是多少？
  4. 这是一个经典的组合数学问题喵！c_g 个人，选 k 个人的方案数是 C(c_g, k)。人数总和就是 Σ_{k=1 to c_g} k * C(c_g, k)。
  5. 根据组合恒等式 Σ_{k=0 to n} k * C(n, k) = n * 2^(n-1)，我们知道这个和就是 c_g * 2^(c_g - 1)！

好耶！S(g) 的计算公式我们找到了，就是 c_g * 2^(c_g - 1)。

从 S(g) 到 T(g) ​

S(g) 统计了所有GCD是 g 的倍数的氏族，也就是说，它包含了GCD是 g, 2g, 3g, ... 的所有情况。 所以，我们有这样的关系： S(g) = T(g) + T(2g) + T(3g) + ...

反过来，我们就可以求出 T(g) 啦！ T(g) = S(g) - (T(2g) + T(3g) + ...)T(g) = S(g) - Σ_{k=2} T(k*g)

看到这个式子，一个绝妙的计算顺序就出现啦：我们从大到小计算 T(g)！ 当我们计算 T(g) 的时候，所有 T(2g), T(3g)... 这些项因为下标更大，所以肯定已经被我们算好了。直接拿来用就好啦！这其实也是一种动态规划的思想呢，喵~

最终的解题步骤 ​

  1. 预处理：
    • 用一个 freq 数组统计每个力量值 a_i 出现了多少次。
    • 预计算 2 的幂次，方便后面使用。
  2. 计算 c_g：
    • 用一个 count_multiples 数组来存储每个 g 对应的 c_g 值。
    • 我们可以用一个类似筛法的循环来高效计算：对于每个 i，遍历它的倍数 j，把 freq[j] 累加到 count_multiples[i] 上。
  3. 计算 T(g) (在代码里是 dp[g])：
    • 从 g = max_A 倒着循环到 2。
    • 先根据公式 c_g * 2^(c_g - 1) 计算出 S(g)。
    • 然后，减去所有已经算好的 T(2g), T(3g), ...。
    • 这样就算出了 T(g)。
  4. 计算总和：
    • 最后，遍历 g 从 2 到 max_A，把 g * T(g) 累加起来，就是我们最终的答案啦！

代码实现喵~ ​

cpp
#include <iostream>

// 定义一些常量，喵~
const int MOD = 1000000007;
const int MAX_A = 1000000;
const int MAX_N = 200000;

// 全局数组，用来存储频率、倍数计数、2的幂和DP表
// +2是为了更安全，虽然+1就够了
int freq[MAX_A + 2];
int count_multiples[MAX_A + 2]; // 这就是我们分析里的 c_g 啦
long long p2[MAX_N + 2];
long long dp[MAX_A + 2]; // 这个就是 T(g) 的说！

// 预处理2的幂，对MOD取模
void precompute_powers(int n) {
    p2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p2[i] = (p2[i - 1] * 2) % MOD;
    }
}

int main() {
    // 快速I/O，让程序跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    int max_val = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        freq[a]++; // 统计每个力量值出现的次数
        if (a > max_val) {
            max_val = a;
        }
    }

    // 预处理2的幂，直到n
    precompute_powers(n);

    // 用类似筛法的方式计算 count_multiples[d]：力量值是d的倍数的士兵总数
    for (int i = 1; i <= max_val; ++i) {
        for (int j = i; j <= max_val; j += i) {
            count_multiples[i] += freq[j];
        }
    }

    // 计算 dp[g]：所有GCD恰好为g的氏族的人数总和，也就是 T(g)
    // 我们使用容斥原理，从最大的g开始向下迭代
    for (int g = max_val; g >= 2; --g) {
        if (count_multiples[g] == 0) { // 如果没有士兵的力量是g的倍数，T(g)肯定是0
            dp[g] = 0;
            continue;
        }
        
        // S(g) = 所有GCD是g的倍数的氏族的人数总和
        // 公式是 c_g * 2^(c_g - 1)
        long long S_g = (long long)count_multiples[g] * p2[count_multiples[g] - 1] % MOD;
        dp[g] = S_g; // 先假设 T(g) = S(g)

        // 减去所有 T(g*k) for k > 1 的贡献，来得到“恰好”是g的贡献
        // T(g) = S(g) - Σ_{k>1} T(g*k)
        for (int m = 2 * g; m <= max_val; m += g) {
            dp[g] = (dp[g] - dp[m] + MOD) % MOD; // 记得加上MOD防止负数
        }
    }

    // 计算军队的总战斗力
    // Σ g * T(g) for all g > 1
    long long total_strength = 0;
    for (int g = 2; g <= max_val; ++g) {
        total_strength = (total_strength + (long long)g * dp[g]) % MOD;
    }

    std::cout << total_strength << std::endl;

    return 0;
}

跑得快不快呀？ ​

  • 时间复杂度: O(N + A_max * log(A_max)) 的说

    • 读取输入和统计频率是 O(N)。
    • 预处理 count_multiples 的两层循环，看起来是 O(A_max^2)，但实际上每个数 j 只会被它的因子 i 访问，所以总操作次数是 Σ_{i=1 to A_max} (A_max / i)，这近似于 A_max * log(A_max)，和调和级数有关喵~
    • 计算 dp 数组的循环也是同理，复杂度也是 O(A_max * log(A_max))。
    • 所以总的时间复杂度就是 O(N + A_max * log(A_max))，完全可以通过！

  • 空间复杂度: O(N + A_max) 的说

    • 我们需要 freq, count_multiples, dp 数组，大小都和 A_max 相关。还需要 p2 数组，大小和 N 相关。所以总空间是 O(N + A_max)。

这次学到了什么喵？ ​

这道题融合了好多有趣的知识点，是一道非常棒的数论练习题呐！

  1. 核心思想：容斥原理 当遇到“恰好是...”这种严格的计数条件时，一个非常强大的思路是先放宽条件为“是...的倍数”，计算出总数，再通过容斥原理减去那些不符合“恰好”条件的部分。

  2. 数论DP 从大到小计算 T(g) 的过程，可以看作是在数论的“倍数关系”上构建的动态规划。dp[g] 的状态依赖于 dp[2g], dp[3g], ... 这些状态，非常巧妙！

  3. 组合数学小技巧 记住 Σ_{k=1 to n} k * C(n, k) = n * 2^(n-1) 这个小公式，在处理“所有子集的size之和”这类问题时超级有用！

  4. 筛法思想 计算 count_multiples 时使用的嵌套循环，是筛法思想的经典应用，能把复杂度从平方级优化到接近线性的对数级。

希望这篇题解能帮助到正在努力的你！继续加油，探索算法世界中更多的奥秘吧，喵~！

Released under the MIT License.

Copyright © 2024-present Moe