9.21
考试，考了源神的题。
P10528 崩坏·星穹铁道
摸你赛的签，矩乘优化 dp 板子。
P3667 Bovine Genomics G
也是个签，但哈希不知道为啥 \(O(n^3log^2n)\) 跑得飞快，太神秘了。
P11660 我终将成为你的倒影
分块好题。
可以将 \(f(x)\) 看成：\(\left \lfloor \frac{x}{b} \right \rfloor\) \(+\) \(\left \lfloor \frac{a}{b} \right \rfloor\) \(+\) \(max(0,(x\) \(mod\) \(b\) \(+\) \(a\) \(mod\) \(b\)) \(-b)\)。
可以发现 \(f(x)==f(y)\) 的必要条件：\(\left | {\left \lfloor \frac{x}{a} \right \rfloor}-{\left \lfloor \frac{y}{a} \right \rfloor}\right |\) \(\le 1\)。
对这个式子分讨一下，可以得出 \(a\) \(mod\) \(b\) 的范围。发现值域很小，并且条件都是区间的形式，考虑差分。这样就可以预处理出每个块内的答案。接下来就很简单了。
时空复杂度均为 \(O(n \sqrt{n})\)，发现空间的瓶颈在于预处理数组。这个数组至于范围很小，改成 \(short\) 类型就好了。
9.22
依然是考试。原创题，不方便放。