期望+莫比乌斯反演。
期望的题，每次都这么神秘啊。
Solution
首先我们先把式子写出来，令$E$是期望，$P$是概率。
$$
\begin{aligned}
E(len) &= \sum_{i \ge 1} P(len=i) \cdot i \\
&= \sum_{i \ge 1} P(len=i) \sum_{j=1}^i \\
&= \sum_{j\ge 1}\sum_{i\ge j} P(len=i) \\
&= \sum_{i\ge 1} P(len \ge i) \\
&= 1 + \sum_{i\ge 1} P(len > i) \\
\end{aligned}
$$
最后的状态是$\gcd_{i=1}^{len}a_i=1$，于是又可推得：
$$
\begin{aligned}
P(len>i) &= P((\gcd_{j=1}^{i}a_i) > 1)\\
&= 1 - P((\gcd_{j=1}^ia_i)=1) \\
&= 1 - \frac{\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_n=1}^m\sum_{d|\gcd_{j=1}^{m}a_j}\mu(d)}{m^i}\\
&= 1- \frac{\sum_{d=1}^m\mu(d)\left \lfloor \frac{m}{d} \right \rfloor^i}{m^i}\\
&= \frac{\sum_{d=2}^m\mu(d)\left \lfloor \frac{m}{d} \right \rfloor^i}{m^i}
\end{aligned}
$$
再带回原式可得：
$$
\begin{aligned}
E(len) &= 1 + \sum_{i\ge 1} P(len > i)\\
&= 1 - \sum_{i\ge 1} \frac{\sum_{d=2}^m\mu(d)\left \lfloor \frac{m}{d} \right \rfloor^i}{m^i}\\
&= 1 - \sum_{d=2}^m \mu(d) \sum_{i \ge 1} (\frac{\left \lfloor \frac{m}{d} \right \rfloor}{m})^i \\
&= 1 - \sum_{d=2}^m \mu(d) \frac{\left \lfloor \frac{m}{d} \right \rfloor}{m-\left \lfloor \frac{m}{d} \right \rfloor}
\end{aligned}
$$
关于最后一步是生成函数的无限项求值。
Code
1 |
|