解题思路

下面给出一种基于“频数 + 前缀和”的解法，其思路是先统计每种木棍长度的出现次数，由于每根木棍长度在 1~5000 之间，因此我们可以构造大小为 5001 的频数数组 cnt，其中 cnt[i] 表示长度为 i 的木棍数量。接着构造前缀和数组 prefix，使得

prefix[i] = cnt[1] + cnt[2] + … + cnt[i]

考虑任取三个木棍，其能组成三角形（满足三边和性质：取排序后记为 x ≤ y ≤ z，其充要条件为 x + y > z）与否。因为木棍均为正数，所以若满足 x + y ≤ z，则一定不能构成三角形。注意：如果三个中有两个等于 z（最大边）则必有 x + z > z，因为 x>0，因此“不能构成三角形”的情况只有当最大边唯一时，即三个木棍排序后为 x, y, z 且 x, y 均严格小于 z 且满足 x + y ≤ z。

因此我们可以枚举“最大边”的长度 z（取值 1~5000），对于固定 z（要求 cnt[z] > 0），再统计所有满足条件的“较短两根木棍”的组合：(x,y)（要求 1 ≤ x ≤ y < z 且 x + y ≤ z）。
对于固定长度 x，注意当 x > z/2 时，因为 x + x > z，就不可能满足 x + y ≤ z。所以只需要枚举 x 从 1 到 floor(z/2)；对于每个 x，令 j 的上界为 jmax = z – x（必有 jmax ≥ x），此时符合条件的 y 值为 [x, jmax]，组合数为

• 当 y = x 时，数量为 C(cnt[x],2)
• 当 y > x 时，数量为 $cnt[x] * (sum_{y=x+1}^{jmax} cnt[y])$

对每个 z，这两部分组合的和乘上 cnt[z] 就是“以 z 为最大边”而构成三角形条件不满足的三根木棍的个数。

最后注意：题目要求求“不能构成三角形的概率”，也就是

$P = (无效三元组数) / (C(n, 3))$

结果需要 mod 1e9+7（这里模数取 1000000007 ），求模意义下的除法需要用乘以分母的逆元（利用费马小定理）。

由于 n 的上界较大（最多 200000），而木棍的取值只有 1~5000，上述双重循环遍历（z 从 1 到 5000，内部 x 从 1 到 floor(z/2)）大约最多 5000×2500≈12.5×10^6 次运算。

代码实现

Python 代码

MOD = 1000000007
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    arr = list(map(int, input().split()))
    MAX = 5000
    # 统计频数，cnt[i]表示木棍长度为i的个数
    cnt = [0] * (MAX + 1)
    for x in arr:
        cnt[x] += 1

    # 构造前缀和数组，prefix[i] = cnt[1] + cnt[2] + ... + cnt[i]
    prefix = [0] * (MAX + 1)
    for i in range(1, MAX + 1):
        prefix[i] = prefix[i-1] + cnt[i]

    # 预先计算6的逆元
    inv6 = pow(6, MOD - 2, MOD)
    
    invalid = 0  # 记录无法构成三角形的组合数
    # 枚举最大边 z
    for z in range(1, MAX + 1):
        if cnt[z] == 0:
            continue
        pairCount = 0  # 对于当前z，统计所有满足 x + y <= z 且 x,y < z 的组合数
        # 枚举较短边 x，从1到 z//2，原因见下面说明：
        # 当 x > z/2 时，因为 x+x > z，就不可能有任何 y 满足 x+y<=z
        for x in range(1, z // 2 + 1):
            jmax = z - x  # y 的上界
            # 1. 当 y = x 时：组合数为 C(cnt[x], 2)
            waysSame = 0
            if cnt[x] >= 2:
                waysSame = (cnt[x] * (cnt[x] - 1) // 2) % MOD
            # 2. 当 y > x 时：y 的取值范围为 [x+1, jmax]
            waysDiff = cnt[x] * (prefix[jmax] - prefix[x]) % MOD
            pairCount = (pairCount + waysSame + waysDiff) % MOD
        # 对于每个 z，将上面的组合数乘以 cnt[z]
        invalid = (invalid + pairCount * cnt[z]) % MOD

    # 计算总三元组数：C(n, 3)
    totalTriples = (n * (n - 1) % MOD * (n - 2)) % MOD
    totalTriples = (totalTriples * inv6) % MOD

    # 求概率 invalid / totalTriples (模意义下除法即乘以逆元)
    result = invalid * pow(totalTriples, MOD - 2, MOD) % MOD
    print(result)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1000000007;
    
    public static void main(String[] args) throws Exception {
        // 使用 BufferedReader 以提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        // 木棍长度范围是1~5000
        int MAX = 5000;
        long[] cnt = new long[MAX + 1];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
            int x = Integer.parseInt(st.nextToken());
            cnt[x]++;
        }
        
        // 构造前缀和数组：prefix[i] = cnt[1] + cnt[2] + ... + cnt[i]
        long[] prefix = new long[MAX + 1];
        prefix[0] = 0;
        for (int i = 1; i <= MAX; i++){
            prefix[i] = prefix[i - 1] + cnt[i];
        }
        
        // 预先计算逆元，注意模数 MOD 为素数
        long inv2 = modPow(2, MOD - 2, MOD);  // 2 的逆元（常数 500000004）
        long inv6 = modPow(6, MOD - 2, MOD);  // 6 的逆元（166666668）
        
        long invalid = 0; // 无效（三根木棍不能组成三角形）的三元组数量
        // 枚举最大边 z（注意只有 z 必须出现在木棍中，即 cnt[z] > 0）
        for (int z = 1; z <= MAX; z++) {
            if (cnt[z] == 0) continue;
            long pairCount = 0; // 统计所有从长度 < z 中选出的 (x, y) 满足 x + y <= z 的组合数
            // x 的取值只需从 1 到 floor(z/2)
            for (int x = 1; x <= z / 2; x++) {
                int jmax = z - x; // y 的最大长度（必须满足 x + y <= z）
                // 若 jmax < x 则没有符合条件的 y，但当 x <= floor(z/2) 时这一条件一定满足
                // 1. 当 y = x 时：数量为 C(cnt[x],2)
                long waysSame = 0;
                if (cnt[x] >= 2) {
                    waysSame = (cnt[x] * (cnt[x] - 1)) % MOD;
                    waysSame = (waysSame * inv2) % MOD;
                }
                // 2. 当 y > x 时：枚举 y 从 x+1 到 jmax 的个数之和（可以用前缀和快速求和）
                long waysDiff = (cnt[x] * ((prefix[jmax] - prefix[x]) % MOD)) % MOD;
                long curr = (waysSame + waysDiff) % MOD;
                pairCount = (pairCount + curr) % MOD;
            }
            // 对于每个 z，所有 (x, y) 对与 cnt[z] 中任取1根组成一个无效三角形（x + y <= z）的组合
            invalid = (invalid + (pairCount * (cnt[z] % MOD)) % MOD) % MOD;
        }
        
        // 总的三元组数：C(n, 3) = n*(n-1)*(n-2)/6
        long totalTriples = (((((long)n * (n - 1)) % MOD) * (n - 2)) % MOD * inv6) % MOD;
        // 求概率：invalid/totalTriples mod MOD，模意义下使用乘以分母的逆元
        long result = (invalid * modPow(totalTriples, MOD - 2, MOD)) % MOD;
        out.println(result);
        out.flush();
        out.close();
    }
    
    // 快速幂取模（计算 base^exp mod mod）
    static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while(exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
 
const long long MOD = 1000000007;
 
// 快速幂取模，计算 base^exp mod mod
long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    const int MAX = 5000;
    // 统计每个长度的出现次数
    vector<long long> cnt(MAX + 1, 0);
    for (int i = 0; i < n; i++){
        int x;
        cin >> x;
        cnt[x]++;
    }
    
    // 构造前缀和数组
    vector<long long> prefix(MAX + 1, 0);
    for (int i = 1; i <= MAX; i++){
        prefix[i] = prefix[i - 1] + cnt[i];
    }
    
    // 预先计算逆元，6的逆元用于计算C(n,3)
    long long inv6 = modPow(6, MOD - 2, MOD);
    long long invalid = 0;
    
    // 枚举最大边 z
    for (int z = 1; z <= MAX; z++) {
        if (cnt[z] == 0) continue;
        long long pairCount = 0;
        // 枚举较短边 x 的取值，只需 x 从 1 到 z/2
        for (int x = 1; x <= z / 2; x++) {
            int jmax = z - x; // y 的上界
            long long waysSame = 0;
            if (cnt[x] >= 2) {
                waysSame = (cnt[x] * (cnt[x] - 1) / 2) % MOD;
            }
            long long waysDiff = cnt[x] * ((prefix[jmax] - prefix[x]) % MOD) % MOD;
            pairCount = (pairCount + waysSame + waysDiff) % MOD;
        }
        invalid = (invalid + pairCount * cnt[z]) % MOD;
    }
    
    // 总三元组数 C(n, 3)
    long long totalTriples = (((long long)n * (n - 1)) % MOD * (n - 2)) % MOD;
    totalTriples = (totalTriples * inv6) % MOD;
    
    // 计算最终答案：invalid / totalTriples (模意义下除法)
    long long result = (invalid * modPow(totalTriples, MOD - 2, MOD)) % MOD;
    cout << result << "\n";
    
    return 0;
}

题目内容

给定$n$ 根木棍，第$i$根木棍的长度为$a_i$。

小红从中选出任意$3$根不同木棍，其中长度可以相同，她希望这$3$根木棍不能组成一个三角形。

现在请你告诉她有多少概率做到，结果对$10^9+7$取模。

提示:本题中，在进行除法的取模时，即计算$(p× q^{-1} mod\ M)$，其中，$q^{-1}$ 可以使用公式$(q^{M-2} mod M)$得到:例如，在计算$\frac{5}{4}$$mod \ M$时，根据公式$4^{-1} = (4^{M-2} mod\ M) = 250\ 000\ 002$，得到$(p× q^{-1} mod\ M)$$= 5 ×250\ 000\ 002\ mod\ M =250\ 000\ 003$。

输入描述

第一行一个整数$n$，表示木棍的数量。

第二行$n$个整数$a_i$，表示第$i$根木棍的长度。

$3≦n≦2×10^5,1≦a_i≦5000$

输出描述

可以证明答案可以表示为一个不可约分数，为了避免精度问题，请直接输出整数$(p × q^{-1} mod\ M)$作为答案，其中$M=(10^9 +7)$$，q^{-1}$是满足$q×q^{-1}≡1\ (mod\ M)$的整数。

更具体地，你需要找到一个整数$x∈[0, M)$满足$x×q$对$M$取模等于$p$。

样例1

输入

4
1 1 1 2

输出

750000006

样例2

输入

3
2 3 4

输出

0

样例3

输入

3
2 6 10

输出

1