题解

问题分析

我们需要统计所有用户对 $(i,j)$（$i < j$），使得在三个特征值 $a$, $b$, $c$ 中，恰好有一个特征值相等，另外两个特征值不相等。

关键思路：容斥原理

设：

• $X$：第一项特征相同的用户对数量
• $Y$：第二项特征相同的用户对数量
• $Z$：第三项特征相同的用户对数量
• $XY$：前两项特征都相同的用户对数量
• $XZ$：第一和第三项特征都相同的用户对数量
• $YZ$：第二和第三项特征都相同的用户对数量
• $XYZ$：三项特征都相同的用户对数量

根据容斥原理，恰好一项特征相同的用户对数量为：

$$\text{答案} = (X + Y + Z) - 2 \times (XY + XZ + YZ) + 3 \times XYZ $$

算法步骤

1. 统计各类相同特征的用户对数量

使用哈希表进行统计：

# 统计单特征相同
count_a = defaultdict(int)  # 按a值分组
count_b = defaultdict(int)  # 按b值分组  
count_c = defaultdict(int)  # 按c值分组

# 统计双特征相同
count_ab = defaultdict(int)  # 按(a,b)分组
count_ac = defaultdict(int)  # 按(a,c)分组
count_bc = defaultdict(int)  # 按(b,c)分组

# 统计三特征相同
count_abc = defaultdict(int)  # 按(a,b,c)分组

2. 计算各类用户对数量

对于每个分组，如果有 $k$ 个用户具有相同的特征值，那么这些用户之间可以形成 $\binom{k}{2} = \frac{k(k-1)}{2}$ 个用户对：

• $X = \sum \binom{\text{count}_a[v]}{2}$
• $Y = \sum \binom{\text{count}_b[v]}{2}$
• $Z = \sum \binom{\text{count}_c[v]}{2}$
• $XY = \sum \binom{\text{count}_{ab}[v]}{2}$
• $XZ = \sum \binom{\text{count}_{ac}[v]}{2}$
• $YZ = \sum \binom{\text{count}_{bc}[v]}{2}$
• $XYZ = \sum \binom{\text{count}_{abc}[v]}{2}$

3. 应用容斥公式

$$\text{答案} = X + Y + Z - 2(XY + XZ + YZ) + 3 \times XYZ $$

复杂度分析

• 时间复杂度：$O(n)$，只需要遍历所有用户一次进行统计
• 空间复杂度：$O(n)$，哈希表存储分组信息

样例验证

样例1

3
1 2 3
1 4 5
1 2 4

统计：

• $X$（a相同）：a=1有3个用户，$\binom{3}{2}=3$
• $Y$（b相同）：b=2有2个用户，$\binom{2}{2}=1$
• $Z$（c相同）：无重复c值，$0$
• $XY$（a,b相同）：(1,2)有2个用户，$\binom{2}{2}=1$，其他组合为0
• $XZ$（a,c相同）：无重复(a,c)对，$0$
• $YZ$（b,c相同）：无重复(b,c)对，$0$
• $XYZ$（a,b,c相同）：无重复三元组，$0$

计算： $3 + 1 + 0 - 2 \times (1 + 0 + 0) + 3 \times 0 = 4 - 2 = 2$ ✓

样例2

4
100 100 100
100 100 100
100 99 99
99 99 100

读者可以自行验证得到答案 5。

实现细节

1. 哈希函数：对于特征值组合，使用元组作为哈希键
2. 组合数计算：使用公式 $C(k,2) = k(k-1)/2$
3. 数据类型：使用 64 位整数避免溢出

总结

本题的核心在于：

1. 将"恰好一个特征相同"的条件转化为容斥原理问题
2. 使用哈希表高效统计各类特征相同的用户对
3. 通过线性算法处理大规模数据

这种方法比直接枚举所有用户对（$O(n^2)$）要高效得多，能够处理 $n \leq 100,000$ 的数据规模。