闲话 10.16
今日第一蚌
Steps to One
已同步更新于 莫比乌斯反演。
CF1139D 用到一点莫反也是莫反。
题目大意：每次从 \(\left[1,n\right]\) 随机取一个数加入数组 \(a_i\)，当 \(gcd_{i=1}^{len}\ a_i = 1\) 时停止，问 \(len\) 的期望。
直接用期望式子推：
\[\begin{aligned}ans&=\sum_{i=1}^{\infty}\ P_{(len=i)}\times i \\ &=\sum_{i = 1}^{\infty}\sum_{j=1}^i\ P_{(len=i)}\\&=\sum_{j=1}^{\infty}\sum_{i\ge j}\ P_{(len=i)}\\&=\sum_{i=1}^{\infty}\ P_{(len\ge i)}\\&=1+\sum_{i=1}^{\infty}\ P_{(len\gt i)}\\&=1+\sum_{i=1}^{\infty}\ P_{(gcd_{j=1}^i\ a_j\gt 1)}\\&= 1+\sum_{i=1}^{\infty}1-P_{(gcd_{j=1}^i\ a_j=1)}\\&=1+\sum_{i=1}^{\infty}1-\frac{\sum_{a_1=1}^n\sum_{a_2=1}^n\cdots\sum_{a_i=1}^n\ \left[gcd_{j=1}^i\ a_j=1 \right]}{n^i}\\&=1+\sum_{i=1}^{\infty}1-\frac{\sum_{a_1=1}^n\sum_{a_2=1}^n\cdots\sum_{a_i=1}^n\ \sum_{d|gcd_{j=1}^i\ a_j}\ \mu{(d)}}{n^i}\\&=1+\sum_{i=1}^{\infty}1-\frac{\sum_{d=1}^n\ \mu{(d)}\ (\lfloor{\frac{n}{d}}\rfloor{})^i}{n^i}\\&=1-\sum_{i=1}^{\infty}\frac{\sum_{d=2}^n\ \mu{(d)}\ (\lfloor{\frac{n}{d}}\rfloor{})^i}{n^i}\\&=1-\sum_{i=1}^{\infty}\frac{1}{n^i}\sum_{d=2}^n\ \mu{(d)}\ (\lfloor{\frac{n}{d}}\rfloor{})^i\\&=1-\sum_{d=2}^n\ \mu{(d)}\sum_{i=1}^{\infty}\left(\frac{\lfloor{\frac{n}{d}}\rfloor{}}{n}\right)^i \end{aligned}
\]
发现最后是个无穷等比数列，可以如下求值：
\[S=\sum_{i=1}^{\infty}\ x^i
\]
\[Sx=\sum_{i=2}^{\infty}\ x^i
\]
\[S-Sx=x
\]
\[S=\frac{x}{1-x}
\]
然后代入即可：
\[\begin{aligned}ans&=1-\sum_{d=2}^n\ \mu{(d)}\frac{\lfloor{\frac{n}{d}}\rfloor{}}{n-\lfloor{\frac{n}{d}}\rfloor{}} \end{aligned}
\]
这道题范围很小，只有 \(10^5\)，\(\mathcal{O(n)}\) 跑就行了，整除分块优化能到 \(\mathcal{O(\sqrt{n})}\)，但筛还是 \(\mathcal{O(n)}\) 的。
代码见 莫反博客。
Updating。