B. 组成三角形 题解

1. 题目回顾

我们有 $n$ 根棍子，第 $i$ 根的长度为 $2^{a_i}$，其中 $a_i$ 是非负整数。我们需要从中选出 $3$ 根棍子组成一个非退化三角形（面积大于 $0$）。求方案数。选取顺序无关。

2. 三角形条件的转化

设三根棍子的长度分别为 $2^x$、$2^y$、$2^z$，不妨假设 $x \le y \le z$。根据三角形不等式，能组成非退化三角形的充要条件是：

由于 $2$ 的幂次增长速度很快，我们来分析不同情况：

情况 1：$x = y = z$

此时 $2^x + 2^x = 2^{x+1} > 2^x$，显然成立。因此任意三根长度相同的棍子都能组成三角形。

情况 2：$x = y < z$

此时不等式变为 $2^x + 2^x = 2^{x+1} > 2^z$，等价于 $z \le x$，但这与假设 $z > x$ 矛盾。所以不存在两短一长的情况能构成三角形。

情况 3：$x < y = z$

此时 $2^x + 2^y > 2^y$ 恒成立（因为 $2^x > 0$）。因此只要有两根较长的棍子长度相等，另一根较短的任意长度都可以构成三角形。

情况 4：$x < y < z$

此时 $2^x + 2^y \le 2^{z-1} + 2^{z-1} = 2^z$，无法严格大于。所以三边长度互不相等时不可能构成三角形。

结论

能构成三角形的三根棍子，其长度指数必须满足以下条件之一：

1. 三个指数全相同；
2. 恰好有两个指数相同（第三个指数可以任意，但由上述分析知第三个指数必须小于或等于相同的指数；若第三个指数等于相同指数，即三个相同，已归入情况1；若小于，则符合 $x<y=z$ 的形式）。

简而言之：选出的 $3$ 个指数不能两两不同。

3. 组合计数方法

设数组 $a$ 中不同值的出现次数分别为 $cnt_1, cnt_2, \dots, cnt_m$（按值从小到大排序）。我们遍历每个不同的值，累加贡献。

对于当前值 $v$，设其出现次数为 $cnt$，在此之前已经遍历过的所有元素总数为 $sum$（即比 $v$ 小的值的出现次数总和）。

• 选择三根长度均为 $v$ 的棍子：贡献为 $\binom{cnt}{3} = \frac{cnt \cdot (cnt-1) \cdot (cnt-2)}{6}$。

• 选择两根长度为 $v$ 的棍子，搭配一根长度小于 $v$ 的棍子：两根长度 $v$ 的选法有 $\binom{cnt}{2} = \frac{cnt \cdot (cnt-1)}{2}$ 种，第三根可从前面 $sum$ 根中任选一根，贡献为 $\frac{cnt \cdot (cnt-1)}{2} \times sum$。

注意：当选择两根长度 $v$ 的棍子并搭配一根长度等于 $v$ 的棍子时，等价于三根长度均为 $v$，已经在第一种情况中计算过，故这里第三根只从小于 $v$ 的棍子中选取，避免重复计数。

遍历完当前值后，将 $cnt$ 累加到 $sum$ 中，继续处理下一个值。

最后输出总方案数。

4. 时间复杂度

• 统计频率需要 $O(n)$ 时间，可以用 map 或排序后计数。
• 遍历不同值的数量不超过 $n$，每次计算 $O(1)$。
• 总时间复杂度 $O(n \log n)$ 或 $O(n)$（取决于统计方式），在 $\sum n \le 3 \times 10^5$ 的限制下完全可行。

5. C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        map<int, int> freq;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            ++freq[x];
        }
        
        long long ans = 0;
        int sum = 0; // 记录比当前值小的元素总数
        for (auto &[val, cnt] : freq) {
            if (cnt >= 3) {
                ans += 1LL * cnt * (cnt - 1) * (cnt - 2) / 6;
            }
            if (cnt >= 2) {
                ans += 1LL * cnt * (cnt - 1) / 2 * sum;
            }
            sum += cnt;
        }
        cout << ans << '\n';
    }
    return 0;
}

6. 样例验证

以样例2为例：$n=4$，数组为 $[3,2,1,3]$。

频率统计：$1 \rightarrow 1$，$2 \rightarrow 1$，$3 \rightarrow 2$。

• 处理 $1$：$cnt=1$，跳过。
• 处理 $2$：$cnt=1$，跳过。
• 处理 $3$：$cnt=2$，$sum=1+1=2$（前面 $1$ 和 $2$ 各 $1$ 个）。贡献为 $\binom{2}{2} \times 2 = 1 \times 2 = 2$。

答案 $2$，与输出一致。

7. 总结

本题的关键是将几何条件（三角形不等式）转化为对指数相等关系的组合条件。利用幂次的性质简化了分类讨论，最终只需简单的组合计数即可求解。代码实现简洁高效。