题意简述

给定 $n$ 个互不相同的整数 $a_i$，求所有无序对 $(i,j)$ 的 $a_i \oplus a_j$ 的十进制位数之和。

关键点

十进制位数 $= \lfloor \log_{10}(x) \rfloor + 1$（对 $x>0$），如果 $x=0$ 则位数为 1，但这里 $a_i$ 互不相同，所以 $a_i \oplus a_j$ 可能为 0 吗？ 只有当 $a_i = a_j$ 时异或为 0，但 $a_i$ 互不相同，所以异或结果不会为 0，因此位数至少为 1。

我们要求：

ans

∑ i < j ( ⌊ log ⁡ 10 ( a i ⊕ a j ) ⌋ + 1 ) ans= i<j ∑ ​ (⌊log 10 ​ (a i ​ ⊕a j ​ )⌋+1)

直接计算不可行

$n \le 5\times 10^4$，$O(n^2)$ 会超时。

思路转换

十进制位数 $k$ 满足：

10 k − 1 ≤ a i ⊕ a j < 10 k 10 k−1 ≤a i ​ ⊕a j ​ <10 k

即：

k

⌊ log ⁡ 10 ( a i ⊕ a j ) ⌋ + 1 k=⌊log 10 ​ (a i ​ ⊕a j ​ )⌋+1 所以 $k$ 只与异或值的大小范围有关。

我们可以按异或值的二进制高位来分组，但这里要求十进制位数，所以最好直接按十进制范围分组。

分组统计

设 $B_k = [10^{k-1}, 10^k - 1]$，那么异或值在 $B_k$ 内的对，其十进制位数就是 $k$。

因此：

ans

∑ k ≥ 1 k ⋅ ( 异或值在 [ 10 k − 1 , 10 k − 1 ] 内的对数 ) ans= k≥1 ∑ ​ k⋅(异或值在 [10 k−1 ,10 k −1] 内的对数)

问题转化为

对每个 $k$，计算有多少对 $(i,j)$ 满足：

10 k − 1 ≤ a i ⊕ a j < 10 k 10 k−1 ≤a i ​ ⊕a j ​ <10 k

利用 Trie 树按位统计

我们可以用 二进制 Trie（01-Trie）来统计异或值在某个区间内的对数。

对于区间 $[L, R)$，我们可以在 Trie 上遍历，统计异或值 $\in [L, R)$ 的数目。

但这里 $L = 10^{k-1}$, $R = 10^k$ 在二进制下不是整齐的 2 的幂，所以直接统计比较麻烦。

更简单的方法：按最高位位置

注意 $10^k \approx 2^{\lfloor k \log_2 10 \rfloor}$，所以十进制位数 $k$ 对应二进制位数大约在 $[ \lceil (k-1) \log_2 10 \rceil, \lceil k \log_2 10 \rceil )$ 之间。

更精确地，$10^{k-1}$ 的二进制位数是 $\lfloor (k-1)\log_2 10 \rfloor + 1$，$10^k - 1$ 的二进制位数是 $\lfloor k \log_2 10 \rfloor$。

我们可以按二进制最高位来分组，然后映射到十进制位数。

算法步骤

对每个 $a_i$，计算它的二进制最高位位置 $b_i$（从 0 开始计数，即 $2^{b_i} \le a_i < 2^{b_i+1}$）。

异或结果的最高位位置 $t$ 等于 $\max(b_i, b_j)$ 或更高，具体取决于它们前缀的相等情况。

更直接的方法： 在 Trie 中插入所有数，然后对每个 $a_i$，在 Trie 中查询与 $a_i$ 异或后结果的最高位位置分布。

高效做法

在 Trie 上遍历时，我们可以记录当前节点下有多少数，并且知道当前异或值的前缀。 当我们知道异或值的二进制长度 $len$ 时，可以推断它的十进制位数 $k$：

二进制长度 $len$ 对应的十进制位数 $k$ 满足：

⌈ l e n ⋅ log ⁡ 10 2 ⌉ ≤ k ≤ ⌊ l e n ⋅ log ⁡ 10 2 ⌋ + 1 ⌈len⋅log 10 ​ 2⌉≤k≤⌊len⋅log 10 ​ 2⌋+1 实际上更精确： 二进制长度 $len$ → 十进制位数 $k = \lfloor (len-1) \cdot \log_{10} 2 \rfloor + 1$。

最终方案

将 $a_i$ 按二进制插入 Trie。

对每个 $a_i$，在 Trie 中遍历，当走到深度 $d$（从高位到低位）时，如果当前异或值的这一位为 1，说明异或值的最高位就是 $d$（从 0 开始），那么它的二进制长度 = $d+1$。

根据二进制长度 $len$ 计算十进制位数 $k$：

k

⌊ ( l e n − 1 ) ⋅ log ⁡ 10 2 ⌋ + 1 k=⌊(len−1)⋅log 10 ​ 2⌋+1 累加 $k \times \text{count}$ 到答案。

时间复杂度

$O(n \cdot 60)$，因为 $a_i \le 10^{18} < 2^{60}$。

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std; using ll = long long;

const int MAXB = 60; // 2^60 > 1e18 const double log10_2 = log10(2);

struct TrieNode { int cnt; TrieNode* ch[2]; TrieNode() : cnt(0) { ch[0] = ch[1] = nullptr; } };

void insert(TrieNode* root, ll x) { TrieNode* cur = root; for (int b = MAXB-1; b >= 0; b--) { int bit = (x >> b) & 1; if (!cur->ch[bit]) cur->ch[bit] = new TrieNode(); cur = cur->ch[bit]; cur->cnt++; } }

ll query(TrieNode* root, ll x) { TrieNode* cur = root; ll ans = 0; for (int b = MAXB-1; b >= 0; b--) { int bit = (x >> b) & 1; // 如果走相反分支，这一位异或结果为1，那么最高位就是b if (cur->ch[bit^1]) { int len = b+1; // 二进制长度 int dec_len = floor((len-1) * log10_2) + 1; ans += dec_len * cur->ch[bit^1]->cnt; } if (!cur->ch[bit]) break; cur = cur->ch[bit]; } return ans; }

int main() { int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) cin >> a[i];

TrieNode* root = new TrieNode();
ll ans = 0;
for (int i = 0; i < n; i++) {
    ans += query(root, a[i]);
    insert(root, a[i]);
}
cout << ans << endl;
return 0;

}

总结

核心是将十进制位数转化为二进制长度，再用 Trie 统计最高位位置。

利用 $\log_{10} 2$ 进行二进制与十进制位数转换。

时间复杂度 $O(n \cdot 60)$，可过 $n \le 5\times 10^4$。