首页 > 其他分享 >ABC272 E~G

ABC272 E~G

时间:2022-11-02 21:36:51浏览次数:76  
标签:Code dfrac 概率 随机 ABC272 单次

E:

考虑最后的答案一定在 \([0,n]\) 中,所以对于每个 \(i\) 都保留它在这个范围内的值。

至多有 \(\sum_{i}\dfrac{n}{i}=n\log n\) 个有效值,用 set 保存下来即可。

Code

F:

咕咕咕,没学过 SA。

G:

随机选择两个数,钦定它们 \(\bmod M\) 后相等,则 \(M\) 为这两个数的差的因数。枚举 \(M\) 然后判断是否合法。

看着很诡异但是来算一算概率就知道了。

因为最终绝对众数的出现次数超过一半,所以第一次随到最终会成为绝对众数的数的概率不小于 \(\dfrac{1}{2}\),第二次也是。

所以单次随机随到正确答案的概率不小于 \(\dfrac{1}{4}\)。

考虑 \((\dfrac{3}{4})^{200}\approx10^{-25}\),比只因先生抽中草神概率还要小。

单次随机复杂度 \(\mathcal O(\sqrt w n)\)。

Code

标签:Code,dfrac,概率,随机,ABC272,单次
From: https://www.cnblogs.com/Kobe303/p/16852517.html

相关文章

  • ABC272 做题笔记
    打得比较漂亮的一场,光速过ABCDE,但是FGH都太过神仙,EX干脆赛时只有两人AC/kkAProblemlink->https://atcoder.jp/contests/abc272/tasks/abc272_a。Solution按题意......
  • abc272_f Two Strings (后缀数组)
    https://atcoder.jp/contests/abc272/tasks/abc272_f将SS#TT在字符串中排序,看标号为1-n后面有多少2n+2-3n+1的标号然后就会注意题目要的是小于等于,那么要拼成SS......