ABC272 E~G
E:
考虑最后的答案一定在 \([0,n]\) 中,所以对于每个 \(i\) 都保留它在这个范围内的值。
至多有 \(\sum_{i}\dfrac{n}{i}=n\log n\) 个有效值,用 set
保存下来即可。
F:
咕咕咕,没学过 SA。
G:
随机选择两个数,钦定它们 \(\bmod M\) 后相等,则 \(M\) 为这两个数的差的因数。枚举 \(M\) 然后判断是否合法。
看着很诡异但是来算一算概率就知道了。
因为最终绝对众数的出现次数超过一半,所以第一次随到最终会成为绝对众数的数的概率不小于 \(\dfrac{1}{2}\),第二次也是。
所以单次随机随到正确答案的概率不小于 \(\dfrac{1}{4}\)。
考虑 \((\dfrac{3}{4})^{200}\approx10^{-25}\),比只因先生抽中草神概率还要小。
单次随机复杂度 \(\mathcal O(\sqrt w n)\)。
原文地址:http://www.cnblogs.com/Kobe303/p/16852517.html
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。