# T614662 三元组 ## 题目描述 给定一个长度为$n$的整数数组$A$,求有多少个三元组$(i,j,k)$**同时满足**以下两个条件。 - $i \lt j \lt k$ - $A_i = A_j = A_k$ ## 输入格式 第一行包含一个整数$n$，表示数组长度。 第二行包含$n$个整数，表示数组$A$. ## 输出格式 输出一个整数，表示符合条件的三元组的数量。 ## 输入输出样例 #1 ### 输入 #1 ``` 12 4 1 5 4 1 1 4 1 5 4 1 1 ``` ### 输出 #1 ``` 24 ``` ## 说明/提示 对于$100\%$的数据,$3 \le n \le 10^6, -10^9 \le A_i \le 10^9$c++

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <unordered_map> using namespace std; // 计算组合数 C(n, 3) long long combination(int n) { // 组合数公式 C(n, 3) = n * (n - 1) * (n - 2) / 6 return (long long)n * (n - 1) * (n - 2) / 6; } int main() { int n; cin >> n; unordered_map<int, int> count; // 用于记录每个元素出现的次数 // 读取数组元素并统计每个元素的出现次数 for (int i = 0; i < n; i++) { int num; cin >> num; count[num]++; } long long result = 0; // 遍历每个元素的出现次数，计算满足条件的三元组数量 for (auto it = count.begin(); it != count.end(); it++) { int freq = it->second; if (freq >= 3) { // 对于出现次数不少于3次的元素，计算其能组成的三元组数量 result += combination(freq); } } cout << result << endl; return 0; } ``` 代码解释： 1. 组合数计算函数 `combination`：该函数用于计算从$n$个元素中选取$3$个元素的组合数，使用公式$C(n, 3) = \frac{n\times(n - 1)\times(n - 2)}{6}$。 2. 统计元素出现次数：使用 `unordered_map` 来记录每个元素的出现次数。遍历输入的数组，对于每个元素，将其在 `unordered_map` 中的计数加$1$。 3. 计算满足条件的三元组数量：遍历 `unordered_map`，对于每个出现次数不少于$3$次的元素，计算其能组成的三元组数量，并累加到结果中。 4. 输出结果：最后输出满足条件的三元组的总数。 额外需要注意的逻辑点： 1. 由于结果可能很大，需要使用 `long long` 类型来存储结果，避免整数溢出。 2. 在计算组合数时，要确保先进行乘法运算，再进行除法运算，以避免整数除法带来的精度损失。 3. 注意检查元素的出现次数是否不少于$3$次，只有出现次数不少于$3$次的元素才能组成满足条件的三元组。 [2025-05-31 14:16:57 | AI写代码神器 | 598点数解答]