宝石项链问题解析
问题理解
我们需要计算宝石项链的美丽值，对于每种颜色的宝石：
* 美丽值 = 颜色值 × 所有该颜色宝石编号的异或和
* 总美丽值 = 所有颜色美丽值的总和
关键概念
异或运算（XOR）：
* 符号：⊕\oplus⊕
* 性质：相同为0，不同为1
* 连续异或：a⊕b⊕c⊕...a \oplus b \oplus c \oplus ...a⊕b⊕c⊕...
算法思路
1. 按颜色分组：使用哈希表（unordered_map）将相同颜色的宝石编号进行异或累积
2. 计算美丽值：对于每种颜色，用颜色值乘以编号的异或和
3. 求和：将所有颜色的美丽值相加
代码实现
算法分析
1. 时间复杂度：O(n)O(n)O(n)
* 读取和处理 nnn 个宝石：O(n)O(n)O(n)
* 遍历哈希表：最坏情况 O(n)O(n)O(n)，平均 O(n)O(n)O(n)
2. 空间复杂度：O(n)O(n)O(n)
* 哈希表最多存储 nnn 个键值对
数学解释
对于颜色 ccc，假设有 kkk 个宝石，编号分别为 i1,i2,...,iki_1, i_2, ..., i_ki1 ,i2 ,...,ik ，则：
* 异或和：x=i1⊕i2⊕...⊕ikx = i_1 \oplus i_2 \oplus ... \oplus i_kx=i1 ⊕i2 ⊕...⊕ik
* 美丽值：c×xc \times xc×x
总美丽值：∑所有颜色 c(c×(⊕i∈颜色c的宝石i))\sum_{\text{所有颜色 } c} (c \times (\oplus_{i \in \text{颜色c的宝石}} i))∑所有颜色 c (c×(⊕i∈颜色c的宝石 i))
样例验证
输入：6 和 3 6 3 6 6 3
颜色3的宝石：编号1, 3, 6
* 异或和：1⊕3⊕6=41 \oplus 3 \oplus 6 = 41⊕3⊕6=4
* 美丽值：3×4=123 \times 4 = 123×4=12
颜色6的宝石：编号2, 4, 5
* 异或和：2⊕4⊕5=32 \oplus 4 \oplus 5 = 32⊕4⊕5=3
* 美丽值：6×3=186 \times 3 = 186×3=18
总美丽值：12+18=3012 + 18 = 3012+18=30 ✓
注意事项
* 使用 long long 防止整数溢出（颜色值最大 10910^9109，异或和最大约 2×1052 \times 10^52×105，乘积最大约 2×10142 \times 10^{14}2×1014）
* 使用 unordered_map 提高查找效率
* 编号从1开始，符合题目要求
