破解 T614662 三元组谜题：O(n) 时间复杂度巧算符合条件三元组数量

要解决这个问题，我们需要统计数组中满足特定条件的三元组 (i, j, k) 的数量，其中 i < j < k 且 A_i = A_j = A_k。关键在于高效地计算每个数值在数组中出现的次数，并利用组合数学来计算可能的三元组数量。 方法思路 1. 统计频率：首先遍历数组，统计每个数值出现的所有位置。可以使用一个字典（哈希表），其中键是数组中的数值，值是该数值在数组中出现的所有位置的列表。 2. 计算三元组：对于每个数值，如果它出现的次数不少于3次，那么我们需要从这个位置列表中任选三个不同的位置 i, j, k，满足 i < j < k。这实际上就是计算从 m 个位置中选取 3 个位置的组合数，即组合数 C(m, 3) = m! / (3! * (m-3)! ) = m*(m-1)*(m-2)/6。 解决代码 ```python import sys from collections import defaultdict def solve(): n = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) value_indices = defaultdict(list) for idx, num in enumerate(A): value_indices[num].append(idx) total = 0 for indices in value_indices.values(): m = len(indices) if m >= 3: total += m * (m - 1) * (m - 2) // 6 print(total) solve() ``` 代码解释 1. 输入处理：使用 `sys.stdin.readline` 来高效读取输入数据，特别是处理大规模数据时。 2. 统计位置：使用 `defaultdict` 来创建一个字典 `value_indices`，其中每个键是数组中的数值，对应的值是该数值在数组中出现的所有位置的列表。 3. 计算组合数：遍历字典中的每个数值的位置列表。如果某个数值出现的次数 `m` 大于等于3次，则计算从这 `m` 个位置中选取3个位置的组合数，并累加到总数 `total` 中。 4. 输出结果：打印最终的三元组数量。 这种方法确保了我们在 O(n) 的时间内统计位置，并在 O(1) 时间内计算每个数值的组合数，总体时间复杂度为 O(n)，适用于给定的约束条件。 额外需要注意的逻辑点 - 确保数值的位置列表是按顺序存储的，这样直接计算组合数即可满足 i < j < k 的条件。 - 使用组合数公式时，注意整数除法可能导致的问题，但在Python中 `//` 运算符会正确处理。 - 处理大数时，Python的整数类型不会溢出，但需要注意输入数据规模可能很大，使用高效的输入方法如 `sys.stdin` 来加速读取。 ######[AI写代码神器 | 606点数解答 | 2025-05-31 14:16:33]