C++实现：计算长度为n序列中元素互不相同的三元组数量

要解决这个问题，我们需要找到满足条件的三元组 (i, j, k)，其中 1 ≤ i < j < k ≤ n，并且 Ai, Aj, Ak 互不相同。我们可以通过以下步骤来实现： 1. 首先计算所有可能的三元组的总数。 2. 然后减去那些不满足条件的三元组，即至少有两个元素相同的三元组。 具体步骤如下： 1. 计算所有可能的三元组的总数：C(n, 3) = n * (n - 1) * (n - 2) / 6。 2. 计算所有不满足条件的三元组的数量。这可以通过统计每个元素的出现次数，然后计算这些元素形成的三元组数量。 以下是C++代码实现： ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; long long countTriplets(int n, vector<int>& A) { unordered_map<int, int> count; for (int num : A) { count[num]++; } long long total = (long long)n * (n - 1) * (n - 2) / 6; long long invalid = 0; for (auto& pair : count) { int cnt = pair.second; if (cnt >= 2) { invalid += (long long)cnt * (cnt - 1) / 2 * (n - cnt); } if (cnt >= 3) { invalid += (long long)cnt * (cnt - 1) * (cnt - 2) / 6; } } return total - invalid; } int main() { int n; cin >> n; vector<int> A(n); for (int i = 0; i < n; ++i) { cin >> A[i]; } long long result = countTriplets(n, A); cout << result << endl; return 0; } ``` 代码解释： 1. `countTriplets` 函数计算满足条件的三元组数量。 2. 使用 `unordered_map` 统计每个元素的出现次数。 3. 计算所有可能的三元组总数 `total`。 4. 计算不满足条件的三元组数量 `invalid`，包括有两个相同元素和三个相同元素的情况。 5. 最终结果是 `total - invalid`。 额外需要注意的逻辑点： - 确保 `n` 的值足够大时，计算结果不会溢出。 - 统计元素出现次数时，使用 `unordered_map` 可以提高效率。 - 计算组合数时，注意使用 `long long` 类型以避免整数溢出。 ######[AI写代码神器 | 565点数解答 | 2025-02-11 11:23:01]