您的当前位置:首页正文

【JZOJ 6087】【GDOI2019模拟2019.3.26】获取名额

2024-11-07 来源:个人技术集锦

Description

n , q ≤ 6 ∗ 1 0 5 , max ⁡ { a i } ≤ 1 0 9 , a n s 精 度 要 求 小 于 1 0 − 6 n,q\leq 6*10^5,\max\{a_i\}\leq 10^9,ans精度要求小于10^{-6} n,q6105,max{ai}109ans106

Solution

min ⁡ { a i } ≤ x \min\{a_i\}\leq x min{ai}x时,ans恒为1,
剩下的显然的有:
A n s i = 1 − ∏ ( 1 − a i x ) Ans_i=1-\prod (1-\frac{a_i}{x}) Ansi=1(1xai)

考虑取对数后泰勒展开,
ln ⁡ ( 1 − a i x ) = − ∑ j = 1 a i j j ∗ x j \ln(1-\frac{a_i}{x})=-\sum_{j=1}\frac{a_i^j}{j*x^j} ln(1xai)=j=1jxjaij

这样就可以对一个区间一起处理了,预处理前几项即可,

然而这样精度可能还有点不够,考虑进一步提升精度

定义阈值 L I LI LI,
对于 a i x ≥ L I \frac{a_i}{x}\geq LI xaiLI的位置,特殊提出来处理,因为就是这样的位置导致精度不够的,
原因:恒有 a i x &lt; 1 \frac{a_i}{x}&lt;1 xai<1,随着次数j的增加, ( a i x ) j (\frac{a_i}{x})^j (xai)j是衰减的,当 a i x \frac{a_i}{x} xai较大时,它的衰减的很慢,也就是出现精度不够情况了,

L I = 0.5 LI=0.5 LI=0.5就差不多了,
可以证明,这样的位置没有很多,因为 a i x \frac{a_i}{x} xai较大意味着 1 − a i x 1-\frac{a_i}{x} 1xai较小,所以如果很多的话很快就衰减到精度以下了

显示全文