解法
题意就是要求：
\[ ( \sum_{i = 1}^n \sum_{j = 1}^n ij gcd(i, j) ) \mod p \]
言简意赅的题面非常舒适。出现了\(gcd\)可以考虑往反演方面思考。先进行例行的套路：枚举\(gcd\)。在这里为了书写方便，我就把取模省去。
莫比乌斯反演与杜教筛
简述
省选级别以上的 OI 赛事中的数学题，相比于 NOIp 的数学题来说要难很多。这篇文章我来记录学习了莫比乌斯反演和杜教筛之后的一些心得。以下是本文大纲：
P3312:「SDOI2014」数表题解
解法
好题。
我们首先写出这道题的暴力解：
\[ 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)\)，我们可以搞出并化简为：
P3830:「SHOI2012」随机树题解
解法
第一问
第一问比较好求，设状态\(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} \]
P3239:「HNOI2015」亚瑟王题解
解法
一道概率期望类 DP。
我们设状态不考虑当前轮数：这样太难设计了，我太菜不会。考虑设计全局的状态：\(f[i][j]\)意义为考虑前\(i\)张卡牌，且游戏结束时只发动了\(j\)张纸牌的概率。那么答案就是：
「Codeforces 113D」Museum 题解
解法
这道题还是挺神仙的，式子比较好推但是高斯消元部分有点麻烦。
首先我们枚举终点\(t\)，设状态\(f[i][j]\)为人在\(i,j\)时转移到\(t\)的概率。考虑下面的式子：