HDU 4609 3-idiots

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4609

题目翻译

给N个长度,问随机选择其中三个长度能组成三角形的概率。

题解

我们可以使用FFT处理出,用任意两个长度组成 K 的数量Sum[K]。
然后接下来,把长度排序,然后根据某个长度在数组中的位置容斥(按照数字大小容斥,好复杂。。推了半天弄不出来,看到题解里按照位置一下子就懂了。)
假设我们现在有一个长度 X(假装他是最长边)
首先两边之和大于第三边,Ans += Sum[k + 1] ~ Sum[maxLen]
然后我们减去这些长度中使用了 X 组成的长度的数量 Ans -= (n – 1)
然后我们减去使大于X和小于X的组成长度的数量 Ans -= (i – 1) * (n – i)
然后我们减去均大于X组成的长度的数量 Ans -= (n – i) * (n – i -1)

代码