多校冲刺 NOIP-20

RT

水博客太快乐了。。。

开题两道期望贴脸，直接看懵了。。。

因为感觉一般概率题都很难，很少有送分的，所以先跳了。。。

于是先看 \(t3\) ，很快写完 \(O(n)\) 做法，但是发现膜数不一定是质数，然后就假了。。。

写了 \(60pts\) 暴力。。。

回来看 \(t2\) ，发现是个 \(SX\) 题，很快写完了。（然而被卡 \(double\) 了。。。

发现 \(t1\) 有 \(40pts\) 部分分，实在太香，写了就没往后想（其实也是个 \(SX\) 题，为什么不想呢？\(40pts\) 太香。。。。

然后想 \(t4\) ，对推式子的能力并不是很自信，于是写了最暴力的 \(30pts\) ，剩下的时间去肝 \(t3\) ，然而到考试结束也没想到用笛卡尔树。。。

\(t1 \ 5pts \ + \ t2 \ 55pts \ + \ t3 \ 60pts \ + \ t4 30pts \ = \ 150pts\)

挂分惨烈，可以说是烤的很差了。。。

\(t1\) 是非常板的一道题，其实只要在想想就可以做出来，但是场上拿了部分分就跑了。。。

没有想到 \(t2\) 会卡 \(double\) ，要用 \(long \ double\) ，但是看数据范围这是理应想到的。。

\(t3\) 想了一下笛卡尔树就去想单调队列了，因为之前做类似的计数题单调队列都可以代替笛卡尔树，还更好写。

\(t4\) 数学推导的能力太差。。。

不难发现，\(B\) 集合中每个数被选概率是一样的，因此对答案的贡献系数也是相同的，只要算出贡献系数既可。

如果一个数在第 \(i\) 次被选，则它对答案的贡献为 \(\sum_{j=i+1}^{n+1} \frac{1}{j}\) ，因此线性求逆元后直接算即可。。

好名字。。。。

假设已经知道后 \(i\) 个生成器生成的数的期望，记为 \(p_i\)，考虑求出后 \(i+1\) 个生成器生成的数的期望，若当前生成器生成的数比 \(p_i\) 大，那么肯定选当前生成器生成的数，反之不选。

笛卡尔树好题。

考虑建出大根笛卡尔树，对于每个节点，它所对的区间的所有子区间都以它为最大值，以此为基础信息合并即可。。

记录巨佬 \(YCX\) 的 \(AK\) 方法。

求：

\[\sum_{i=1}^n \mu(i)^2 i

\]

曾经一道题中出现过如下式子：

\[\mu(i)^2 = \sum_{d^2 | i} \mu(d)

证明略（巨佬 \(zjjjjjjjjjjj\) 只用 \(\frac{1}{inf} min\) 就证出来了。。。

则

\[ans= \sum_{i=1}^n i \sum_{d^2 | i} \mu(d)

\[=\sum_{d=1}^{\sqrt{n}} \mu(d) \sum_{d^2 | i} i

\[=\sum_{d=1}^{\sqrt{n}} \mu(d) \frac{d^2+d^2 \lfloor \frac{n}{d^2} \rfloor}{2} \lfloor \frac{n}{d^2} \rfloor

\[=\sum_{d=1}^{\sqrt{n}} \mu(d) d^2 S(\lfloor \frac{n}{d^2} \rfloor)

其中

\[S(n)=\sum_{i=1}^n i

这样便可以通过整除分块解决此题。