#P3513. [MUTC2013]idiots

    ID: 2725 传统题 1500ms 128MiB 尝试: 1763 已通过: 375 难度: 7 上传者: 标签>难度分类提高+/省选-组合数学补集计数多项式与生成函数卷积转化NTT数论中国剩余定理重复元素除重排序与序列处理一维前缀和数值计算与优化定点数十进制舍入CF2200Bysbullet

[MUTC2013]idiots

[MUTC2013] idiots

题目描述

有 nn 根木棒,第 ii 根的长度为 aia_i。从中等概率地选出由三根不同木棒组成的一组。即使两根木棒一样长,它们仍是不同的木棒。

求所选三根木棒能组成非退化三角形的概率。也就是说,三根木棒中较短的两根长度之和必须严格大于最长的一根。

输入格式

第一行一个整数 TT,表示数据组数。

接下来每组数据占两行。第一行一个整数 nn,第二行有 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

每组数据输出一行概率,四舍五入保留小数点后恰好 77 位。

样例 #1

2
4
1 3 3 4
4
2 3 3 4
0.5000000
1.0000000

第一组共有四种选法。两种选到长度 1,3,41,3,4 的选法均无法组成非退化三角形,余下两种可以。第二组的四种选法都可以。

数据范围

1≤T≤201\le T\le20,3≤n≤1053\le n\le10^5,1≤ai≤1051\le a_i\le10^5。