题目内容

给定$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$。

解题思路

下面给出一种基于“频数 + 前缀和”的解法，其思路是先统计每种木棍长度的出现次数，由于每根木棍长度在 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。