10.13
咕咕咕。
upd-10.18
补了一下[Ynoi2016]炸脖龙I。
显然是数据结构题Ynoi能不是吗。
看见这个幂塔，就可以想到拓展欧拉定理。发现\(a^p\equiv a^{\varphi(p)}\),而\(\begin{matrix}\underbrace{\varphi(\varphi(...\varphi(x)...))}\\O(\log n)\end{matrix}\)就可以等于\(1\)，因为不难证明\(\varphi(i)\equiv 0(\mod 2)或\varphi(i)\le\frac{i}{2}\)，所以暴力套\(\varphi(\varphi(...\varphi(x)...))\)是可以的。对于长度过短的区间，直接暴力即可。如果区间有\(1\)，后面的直接不用算了，更简单。
区间修改很容易，分治数据结构即可。
10.14
P6902
怎么倍增题永远想不到倍增呢。
简化到链上，发现就是一个经典的贪心模型。考虑把它转移到环上。
首先我们想到可以断环成链。将区间复制一份，然后计算每个区间的后继，可以通过排序简化计算。
然后预处理每一个区间的\(2^i\)级后继，再对每一个\(1\)至\(n\)的位置查询答案。
时间复杂度\(O((n+k)logn)\)。
P6835
怎么这么简单的期望入门题就想不到呢。
根据我们一般的经验，我们可以想到设\(dp_{i}\)为从第\(i\)个节点到第\(i+1\)个节点的期望步数。根据期望的线性性，我们可以得出从\(1\)到\(i\)的期望步数。
考虑返祖边。如果某个点如果返祖的话，就要再走一遍祖先到这个点的路，外加返祖边的贡献，即\(1+\sum_{i=v}^udp[i]\)，求和的部分可以用前缀和优化。设 \(sum_i=\sum_{j=1}^if[i]\)。
则状态转移方程为：\(dp_i=\sum_{i\to v}(sum_{i-1}-sum_{v-1}+1)+1\)。
时间复杂度\(O(n+m)\)。
10.15
P1948
怎么二分题永远想不到二分呢。
二分最大答案。
P6190
终于想到矩阵快速幂了。
式子太复杂了。
10.16
P3065
发现如果一个单词想要成为字典序最小的单词，那么这个单词不能有前缀是另一个单词，并且这个单词与其他单词的对应不能出现环，如a比b大并且b比a大。判断用字典树和判环即可。
P3732
Trie预处理，发现数据随机，猜想答案不会太大。
10.18
P1559
SA！！！！！！！
P1337
SA！！！！！！！！！！！！！！！！！
P2291
分讨。
P5043
裸哈希，带重心。
10.19
比赛。
T1开的很顺，T2也是。T3写个线段树写好了，看T2又崩了，调不好了，挂了80.最后220，百分之6.