峡国西高校 (hard version) - 题解

标签与难度

标签: 贡献法, 拆位, 组合数学, 数论, 模运算难度: 2100

题目大意喵~

主人你好呀，这道题是说，我们有一个长度为 $n$ 的序列 $\{a_i\}$ ，还有一个整数 $k$ 。我们需要定义一种新的运算，叫做“ $k$ 进制异或”，它其实就是 $k$ 进制下的不进位加法，喵~

具体来说，对于两个数 $x$ 和 $y$ ，我们将它们都转换成 $k$ 进制。对于每一位，我们将对应位上的数字相加，然后对 $k$ 取模，得到结果在这一位上的数字。所有位的计算结果组合起来，就是 $x$ 和 $y$ 的 $k$ 进制异或和，我们记作 $x \oplus_k y$ 。

我们的任务是，计算出这个序列中所有不同的数对 $(a_i, a_j)$ （也就是 $i \ne j$ ）的 $k$ 进制异或和的总和。因为结果可能会很大，所以要对 $10^9 + 7$ 取模，呐。

举个栗子：如果 $k=10$ ，那么 $15 \oplus_{10} 27$ 是多少呢？ $15$ 的十进制是 15， $27$ 的十进制是 27。个位： $(5+7) \pmod{10} = 2$ 十位： $(1+2) \pmod{10} = 3$ 所以 $15 \oplus_{10} 27 = 32$ 。

我们要计算的就是 $\sum_{1 \le i < j \le n} (a_i \oplus_k a_j)$ 的值，喵~

解题思路分析

看到要计算所有数对的和，最直接的想法就是暴力枚举，喵！我们可以写一个两层循环，遍历所有 $1 \le i < j \le n$ 的数对，计算它们的 $k$ 进制异或和，然后累加起来。但是看看数据范围， $n$ 最大有 $2 \times 10^6$ ，这样 $O(n^2)$ 的复杂度肯定会超时的说。我们必须找到更快的办法，呐。

这种涉及位运算（或者类似位运算）的求和问题，一个非常经典和强大的思路就是拆位贡献法。就像我我喜欢把小鱼干拆开一点点吃一样，我们也可以把一个大问题拆成许多小问题来解决！

一个数 $A$ 可以表示成 $k$ 进制的形式： $A = \sum_{d=0}^{\infty} A_d \cdot k^d$ ，其中 $A_d$ 是 $A$ 在 $k$ 进制下第 $d$ 位（从右往左，从0开始）的数字。那么， $a_i \oplus_k a_j$ 的值就是：

a_i \oplus_k a_j = \sum_{d=0}^{\infty} ((a_{i,d} + a_{j,d}) \pmod k) \cdot k^d

其中 $a_{i,d}$ 是 $a_i$ 的第 $d$ 位数字。

我们要计算的总和是 $\sum_{1 \le i < j \le n} (a_i \oplus_k a_j)$ 。利用上面这个式子，我们可以把求和符号交换一下位置：

\text{TotalSum} = \sum_{1 \le i < j \le n} \sum_{d=0}^{\infty} ((a_{i,d} + a_{j,d}) \pmod k) \cdot k^d

= \sum_{d=0}^{\infty} k^d \cdot \left( \sum_{1 \le i < j \le n} (a_{i,d} + a_{j,d}) \pmod k \right)

看！现在问题就转化成：对于每一个位 $d$ ，我们计算出所有不同数对在这一位上的数字之和（模 $k$ 之后的结果），我们称之为 DigitSum_d，然后乘以权重 $k^d$ ，最后把所有位的贡献加起来。

对于固定的某一位 $d$ ，我们怎么高效地计算 DigitSum_d 呢？ DigitSum_d = \sum_{1 \le i < j \le n} (a_{i,d} + a_{j,d}) \pmod k

为了方便，我们把第 $d$ 位上的数字 $a_{i,d}$ 记作 $v_i$ 。现在我们有 $n$ 个数字 $v_1, v_2, \dots, v_n$ ，它们都在 $[0, k-1]$ 范围内。我们的目标是计算 $\sum_{1 \le i < j \le n} (v_i + v_j) \pmod k$ 。

这个式子里的 $\pmod k$ 有点讨厌，我们想办法处理掉它。当 $v_i + v_j < k$ 时， $(v_i + v_j) \pmod k = v_i + v_j$ 。当 $v_i + v_j \ge k$ 时， $(v_i + v_j) \pmod k = v_i + v_j - k$ 。

所以，我们可以把求和式改写成：

\text{DigitSum}_d = \sum_{1 \le i < j \le n} (v_i + v_j) - k \cdot (\text{满足 } v_i+v_j \ge k \text{ 的不同数对 } (i,j) \text{ 的数量})

这个式子分为两部分，我们分别来求：

第一部分: $\sum_{1 \le i < j \le n} (v_i + v_j)$ 这个求和可以这样变形：

\sum_{1 \le i < j \le n} (v_i + v_j) = \frac{1}{2} \sum_{i \ne j} (v_i + v_j)

考虑每个 $v_i$ 会被加多少次。在 $i \ne j$ 的所有求和中，每个 $v_i$ 都会和另外 $n-1$ 个 $v_j$ 配对，所以它出现了 $n-1$ 次。因此， $\sum_{i \ne j} (v_i + v_j) = \sum_{i=1}^n (n-1) v_i = (n-1) \sum_{i=1}^n v_i$ 。所以第一部分就是 $\frac{(n-1) \sum_{i=1}^n v_i}{2}$ 。等一下，这个除以2好像很麻烦，我们先不这么算。让我们直接计算 $\sum_{1 \le i < j \le n} (v_i + v_j)$ 。它等于 $\sum_{i=1}^n (n-1) v_i = (n-1) \sum_{i=1}^n v_i$ 。 Wait a minute, that's not right, nya~ 让我重新捋一捋... 啊！ $\sum_{1 \le i < j \le n} v_i$ 中，每个 $v_i$ 会和 $n-1-i$ 个 $v_j$ ( $j>i$ ) 配对。 $\sum_{1 \le i < j \le n} v_j$ 中，每个 $v_j$ 会和 $j-1$ 个 $v_i$ ( $i<j$ ) 配对。这太复杂了！还是用刚才的思路：每个 $v_i$ 在所有不同数对中出现了 $n-1$ 次。所以总和就是 $(n-1) \sum_{i=1}^n v_i$ 。嗯，这次对了！

第二部分: 满足 $v_i+v_j \ge k$ 的不同数对 $(i,j)$ 的数量 要计算这个，我们可以先统计出每个数字 $u \in [0, k-1]$ 出现的次数，记为 count[u]。然后，我们可以枚举所有可能的数字对 $(u, v)$ ，其中 $0 \le u, v < k$ 且 $u+v \ge k$ 。

如果 $u \ne v$ ，那么从 count[u] 个数中选一个，从 count[v] 个数中选一个，有 count[u] * count[v] 种配对。
如果 $u = v$ （也就是 $2u \ge k$ ），那么从 count[u] 个数中选两个，有 count[u] * (count[u] - 1) / 2 种配对。

把这些情况加起来，就是我们想要的数量。这个计算有点繁琐，我们换个角度，喵~ 令 WrapAllPairs 为所有数对 $(i, j)$ （包括 $i=j$ ）中满足 $v_i+v_j \ge k$ 的数量。 WrapAllPairs = \sum_{u=0}^{k-1} \sum_{v=0}^{k-1} [u+v \ge k] \cdot \text{count}[u] \cdot \text{count}[v]$ 令 WrapSelfPairs为满足 $v_i+v_i \ge k$ 的数量。WrapSelfPairs = \sum_{u=0}^{k-1} [2u \ge k] \cdot \text{count}[u]$ 那么我们要求的不同数对的数量 WrapDistinctPairs 就是： WrapDistinctPairs = (WrapAllPairs - WrapSelfPairs) / 2 这里有个小技巧哦：WrapAllPairs - WrapSelfPairs 的结果一定是偶数，所以可以直接用整数除法，不需要求模逆元，很方便！

好了，现在我们把所有零件都准备好了！对于每一位 $d$ ：

遍历所有 $n$ 个数，得到它们在第 $d$ 位的数字 $v_i$ ，并统计出 count[0...k-1]。
计算 $\text{SumOfDigits} = \sum_{i=1}^n v_i = \sum_{u=0}^{k-1} u \cdot \text{count}[u]$ 。
计算 WrapDistinctPairs 的数量。
该位的总贡献（不含 $k^d$ ）就是 (n-1) * SumOfDigits - k * WrapDistinctPairs。
将这个贡献乘以 $k^d$ 再加到最终答案里。

我们从第 $0$ 位开始，一位一位地处理，直到所有数都变成0为止。整个算法的复杂度是 $O(\text{max_digits} \cdot (n + k^2))$ ，完全可以接受，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 使用 long long 防止计算过程中溢出
using ll = long long;

// 模数
const int MOD = 1e9 + 7;

int main() {
    // 加速 C++ 的 I/O，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ll n;
    int k;
    std::cin >> n >> k;

    std::vector<ll> a(n);
    bool has_positive_number = false;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] > 0) {
            has_positive_number = true;
        }
    }

    ll total_ans = 0;
    ll k_power_mod = 1; // 代表 k^d mod MOD

    // 只要还有非零的数，就继续处理下一位
    for (int d = 0; has_positive_number; ++d) {
        has_positive_number = false; // 假设这一轮后所有数都为0

        // 1. 统计当前位上 0 到 k-1 各数字的出现次数
        std::vector<ll> digit_counts(k, 0);
        for (ll val : a) {
            digit_counts[val % k]++;
        }

        // 2. 计算当前位所有数字的总和
        // SumOfDigits = sum(v_i) = sum_{u=0}^{k-1} u * count[u]
        ll sum_of_digits = 0;
        for (int u = 0; u < k; ++u) {
            sum_of_digits = (sum_of_digits + (ll)u * digit_counts[u]) % MOD;
        }

        // 3. 计算满足 v_i + v_j >= k 的不同数对 (i,j) 的数量
        // 先计算所有数对 (i,j) 的，包括 i=j
        ll wrap_all_pairs = 0;
        for (int u = 0; u < k; ++u) {
            for (int v = 0; v < k; ++v) {
                if (u + v >= k) {
                    wrap_all_pairs += digit_counts[u] * digit_counts[v];
                }
            }
        }
        // 再计算 i=j 的情况
        ll wrap_self_pairs = 0;
        for (int u = 0; u < k; ++u) {
            if (u + u >= k) {
                wrap_self_pairs += digit_counts[u];
            }
        }
        // 得到不同数对的数量，这里一定是偶数，所以可以直接除以2
        ll wrap_distinct_pairs_count = (wrap_all_pairs - wrap_self_pairs) / 2;

        // 4. 计算当前位的总贡献
        // sum_{i<j} (v_i+v_j)
        ll sum_values_distinct = ((n - 1) % MOD * sum_of_digits) % MOD;
        // 减去 wrap 产生的 k
        ll wrap_penalty = ( (ll)k * (wrap_distinct_pairs_count % MOD) ) % MOD;

        ll digit_contribution = (sum_values_distinct - wrap_penalty + MOD) % MOD;

        // 5. 累加到总答案
        total_ans = (total_ans + digit_contribution * k_power_mod) % MOD;

        // 6. 准备下一位的计算
        k_power_mod = (k_power_mod * k) % MOD;
        for (ll &val : a) {
            val /= k;
            if (val > 0) {
                has_positive_number = true; // 发现还有非零数，需要继续
            }
        }
    }

    std::cout << total_ans << "\n";

    return 0;
}

复杂度分析

时间复杂度: $O(D \cdot (N + K^2))$
- 我们需要对每一位进行计算。最大数是 $10^{18}$ ，所以总共的位数 $D$ 大约是 $\log_k(10^{18})$ 。由于 $k \ge 2$ ，所以 $D$ 最多在 60-70 这个数量级。
- 在每一位的计算中，我们需要：
  - 遍历 $N$ 个数来统计各位数字的出现次数，复杂度是 $O(N)$ 。
  - 计算 wrap_all_pairs 时，有一个 $k \times k$ 的循环，复杂度是 $O(K^2)$ 。
  - 其他计算都是 $O(K)$ 或者 $O(1)$ 。
- 因此，总的时间复杂度是 $O(D \cdot (N + K^2))$ ，这对于给定的数据范围是完全足够的，喵~
空间复杂度: $O(N+K)$
- 我们需要一个大小为 $N$ 的数组 a 来存储输入的数字。
- 在每次循环中，我们还需要一个大小为 $K$ 的 digit_counts 数组来统计数字。
- 所以总的空间复杂度是 $O(N+K)$ 。

知识点总结

这道题是“拆位贡献”思想的一个非常好的应用，喵~ 这种思想在处理和位运算相关的数组问题时特别有用。

拆位/拆分贡献: 当一个问题的整体计算很复杂，但可以分解成各个独立部分（比如二进制的每一位，或 $k$ 进制的每一位）的贡献之和时，就可以使用这种方法。将复杂问题简单化。
组合计数: 在计算每一位的贡献时，我们用到了组合计数的思想。通过统计每种数字的出现次数，而不是直接处理原始数字，大大降低了计算的复杂度。
公式推导与转换: 核心在于将 $(v_i + v_j) \pmod k$ 这个式子转换成 $\sum (v_i+v_j) - k \cdot (\text{wrap_count})$ 的形式，这样就剥离了复杂的模运算，让问题变得清晰。
避免模逆元的小技巧: 在计算不同数对的 "wrap" 数量时，通过 (AllPairs - SelfPairs) / 2 的方式，利用其结果必为偶数的性质，避免了在模意义下求2的逆元，让代码更简洁、更安全。

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦，喵~

峡国西高校 (hard version) - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​