BZOJ 3513 [MUTC2013]idiots

发布于 2017-08-15  172 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3513

题意:给定 n 个长度分别为\(a_i\) 的木棒,问随机选择 3 个木棒能够拼成三角形的概率。


显然可以用生成函数记录每种长度的出现次数。生成函数自己对自己做多项式乘法即选择两个的方案,注意此处有选择两个自己的重复情况。

由于是等概率取,答案乘一个 C(n,3),统计不同方案数即可。

一次取两个,只要大于等于这两个的和的都不合法,前缀和统计即可。

学习了一个迭代版 fft...

 

 


一个非常弱的准退役OIER