4/5
差一个splay
题目链接
D
题意
给一个 $m$，每次可以从 $[1,m]$ 中选择一个数，直至 $gcd$ 为 1，问期望长度。
分析
- 显然选的第一个数很关键。
- 考虑第一个数为 $k$，要想序列gcd不为1，那么选的其他数字都要为都要包含至少包含k的一个素因子。
- 那么现在我们从[1,m]，从小到大考虑每一个数，那么我们考虑2的倍数，3的倍数，必然都会包含6，这个地方容斥需要莫比乌斯函数。
- 考虑长度的期望 $E(x) = (1-p) · 1 + p · (1 - p) · 1 + p^2 · (1-p)+…$
- 会发现这里的长度至少为1，则 $ans = 1 + \sum_{i=1}^{m}·E(i)·mu(i)·-1$。
- 事实上这个期望是一个负二项分布，设成功的概率为p，那么r次失败前需要的期望次数： $E(x) = \frac{rp}{1-p}$
- 这道题的 $p$ 是 $n/i$，$r$ 是 $1$。
E
倒着动态加边的二分图最大匹配，匈牙利即可。
F
spaly咕咕咕。