题意

给出\(n\)个木棍,求任意选出三根能组成三角形的概率。

分析

考虑每一个木棍,长度为\(x\),想知道它为三条边中的最长边时的方案数,显然要知道某两根加起来长度大于它的情况。

这里用卷积可以得到两两加和以后的情况。

对于直接卷积得到的结果,自己+自己的应该出去,然后显然当前是总方案数的两倍,除以\(2\)。

这样一来,对于每一个作为最长边的方案数就是卷积结果大于它的数量。

但很显然这样是有一些情况不满足要求的,具体分为下面三类:

  • 两条都比它大的加在一起
  • 一条比它大,另一条比它小的加在一起
  • 任意一条和它自己加在一起

这三种情况,在排序以后可以\(O(1)\)算出来,除掉即可。

 

Categories: 数学FFT

发表评论

电子邮件地址不会被公开。 必填项已用*标注