莫比乌斯反演与杜教筛

简述

省选级别以上的 OI 赛事中的数学题，相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲：

好题。

我们首先写出这道题的暴力解：

\[ answer = \sum_{i = 1}^n \sum_{j = 1}^m \sigma_1 (gcd(i, j)) [\sigma_1 (gcd(i, j)) \leq limit] \]

复杂度超级大，怎么办？换一种思维来写这个式子，考虑枚举每一个\(gcd(i, j)\)为\(d\)，记起次数为\(g(d)\)，我们可以搞出并化简为：

第一问比较好求，设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献，可以知道：

\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]

一道概率期望类 DP。

我们设状态不考虑当前轮数：这样太难设计了，我太菜不会。考虑设计全局的状态：\(f[i][j]\)意义为考虑前\(i\)张卡牌，且游戏结束时只发动了\(j\)张纸牌的概率。那么答案就是：

这道题还是挺神仙的，式子比较好推但是高斯消元部分有点麻烦。

首先我们枚举终点\(t\)，设状态\(f[i][j]\)为人在\(i,j\)时转移到\(t\)的概率。考虑下面的式子：

这道 DP 出的很好，考察了选手模型转换的能力。

第\(i\)个人说：“有\(ai\)个人分数比我高，\(bi\)个人分数比我低。”

每一句话都可以看作是一维坐标上的一条线段\([a_i+1,n-b_i]\)，表示这一段线段上的人成绩相等。显然，对一每一种合法情况，这些线段都不会相交（允许完全重合）。所以将线段按左端点排序，这个以坐标位关键字的\(dp\)方程应该写成：

\[ dp[i] = dp[i-l] + min(\text{线段长度}, \text{线段个数}) \]