模拟赛不知道对于 \(d(n)\) 很大的数可以做根号质因数分解，直接输完了。
中午在外面吃饭，去了一家很有创意和技术的餐馆，西安菜还是有辣的，而且还挺不错。
晚上看 RMR，A 队进了，小蜜蜂能不能进呢，不知道。
跳跃
DP 形式形如高维偏序，于是考虑怎么样来做这个东西。
常规做法有点菜，考虑高维前缀和 + 根号重构，于是可以在根号复杂度内求出一个点的答案，就可以过了。
注意对于 \(d(n)\) 较大的数可以暴力根号质因数分解。
https://marsoj.cn/record/65d5b99793e87304eedf9aa6
随机游走
令 \(g_u\) 表示只走 \(1\) 边到终点 \(T\) 的概率，\(f_u\) 表示 \(u\) 的期望权值。
则 \(g_u=\frac{1}{deg_u}\sum_{w=1}g_v\)，\(f_u=\frac{1}{deg_u} (\sum_{w=1}(f_v+g_v)+\sum_{w=0}f_v)\)。
可以高斯消元解出。
考虑求方差，由高中数学 \(D(x)=E(x^2)-E^2(x)\)，于是考虑怎样求 \(E(x^2)\)。
令事件 \(C\) 表示 \(x\) 向后走的过程中走到了 \(0\)，\(C_R\) 为 \(C\) 的反事件，则有：
\(p_v(C)E_v(x^2|C)+p_v(C_R)E_v(x^2|C_R)\) 可以合并成 \(E_v(x^2)\)，于是只需要求 \(E_u(x^2)\)，\(2p_u(C_R)E_v(x|C_R)\)，\(p_u(C_R)\)，可以列出大小为 \(3*n\) 的方程。
高斯消元即可，\(O(n^3)\)。
https://marsoj.cn/record/65d5c7e993e87304eedfa506
随机取数
利用期望的线性性，考虑计算某一个数的贡献。
枚举 \(x\)，对于 \(x\) 的贡献则要求其后面的数不被全部拿完，令 \(f_{i,j,k}\) 表示选了 \(j\) 个 \(\le a_i\) 的数，其中有 \(k\) 个还要往后丢。
枚举选了 \(t\) 个 \((a_i,a_{i+1}]\) 里面的数，如果 \(k+t\) 不为 \(0\)，则会有一个数拿掉 \(a_{i+1}\)。
如果 \(x\le a_i\) 且 \(k+t=0\)，则 \(x\) 就可以和 \(a_i\) 匹配了，于是就可以计入贡献。
注意到我们不用真的枚举 \(x\)，可以记录下来一个 \(0/1/2\) 表示 \(x\) 是否选定，与 \(x\) 合并的数是否出现，于是可以做到 \(O(n^4)\)。
感觉还有很多细节。
https://marsoj.cn/record/65d60f0593e87304eedfd182