洛谷P6686题解：组合数学在等腰三角形计数中的应用

5个月前 (08-07)洛谷题解235

一、问题背景

洛谷P6686题目要求计算使用给定长度木棍能组成的不同等腰三角形的数量。通过组合数学和三角形不等式，我们可以高效解决这一计数问题。

二、算法核心思想

问题分析：等腰三角形需满足两边相等且第三边满足三角形不等式
组合数学：使用频率统计和组合数公式计算可能情况
优化策略：排序+二分查找快速确定有效范围

三、完整代码实现(带详细注释)

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

const int MOD = 998244353; // 题目要求的模数

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    unordered_map<int, int> freq; // 记录每个长度出现的频率
    
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        freq[a[i]]++; // 统计每种长度的出现次数
    }
    
    sort(a.begin(), a.end()); // 排序便于二分查找
    
    long long ans = 0; // 最终结果
    
    // 处理两条边相等的情况（等腰但不全等）
    for (auto it = freq.begin(); it != freq.end(); ++it) {
        int len = it->first;
        int cnt = it->second;
        
        if (cnt >= 2) { // 至少需要两根相同长度的木棍
            int max_len = 2 * len - 1; // 三角形不等式：x < 2*len
            
            // 使用upper_bound找到第一个大于max_len的位置
            auto upper = upper_bound(a.begin(), a.end(), max_len);
            
            // 计算满足条件的木棍总数
            int total = upper - a.begin();
            
            // 减去相同长度的木棍（避免三根相同的情况）
            total -= cnt;
            
            // 组合数计算：C(cnt,2) * total
            long long combinations = (long long)cnt * (cnt - 1) / 2 % MOD;
            ans = (ans + combinations * total % MOD) % MOD;
        }
    }
    
    // 处理三根边都相等的情况（等边三角形）
    for (auto it = freq.begin(); it != freq.end(); ++it) {
        int cnt = it->second;
        if (cnt >= 3) {
            // 组合数计算：C(cnt,3)
            long long combinations = (long long)cnt * (cnt - 1) * (cnt - 2) / 6 % MOD;
            ans = (ans + combinations) % MOD;
        }
    }
    
    cout << ans << endl;
    return 0;
}