各种 trick……
数据结构常见套路
- 去 log 的套路：
- 可持久化。
- 线段树上二分 / 树状数组上倍增。
- 处理子树的套路：
- 如果信息有区间减法 / 带修改，首选 DFS 序。
- 线段树合并。
莫比乌斯反演常见套路
- 如果题目的式子跟 gcd 有关，优先考虑莫反。
- \mu * 1 = \epsilon 比莫比乌斯反演公式快很多（指推导的时候）。
- 如果有枚举约数的，尽量考虑把它提到式子最前面。
- 对所有数对的 \gcd 算一个式子时，考虑枚举 \gcd 并算它贡献的次数。
- 当 \gcd(x,y) > 1 时，\mu(xy) = 0。
一些公式
- \sum\limits_{i = 1}^n i = C_{n + 1}^2 = \dfrac {n (n + 1)} 2
- \sum\limits_{i = 1}^n i^2 = C_{n + 1}^2 + 2C_{n + 1}^3 = \dfrac {n (n + 1) (2n + 1)} 6
- \sum\limits_{i = 1}^n i^3 = C_{n + 1}^2 + 6C_{n + 1}^3 + 6C_{n + 1}^4 = \dfrac {n^2 (n + 1)^2} 4
某 border 结论证明
以下设 n = |S|。
弱周期引理
设 p,q 为 S 的周期，p + q \le n，则 \gcd(p,q) 也是 S 的周期。
不妨设 p > q，则令 d = p - q。
对于 i - q > 0，有 S_i = S_{i-q} = S_{i+p-q} = S_{i+d}。
对于 i + p \le n，有 S_i = S_{i+p} = S_{i+p-q} = S_{i+d}。
当 p + q \le n 时不存在 i 同时不满足以上两者。
引理
S 的所有长度不小于 \frac n2 的 border 的长度为一个等差数列。
设 p 为 S 的最小周期，不妨设 p \le \frac n2。
设 q 为 S 的一个周期，满足 q \le \frac n2。
则由弱周期引理可知 \gcd(p,q) 同为 S 的周期。
由上可知 \gcd(p,q) \ge p。
故显然 p \mid q。
证明
字符串 S 的所有 border 按长度排序后可以划分为 O(\log n) 段等差数列。
将 S 的 border 长度 x 分类为 [1,2),[2,4),\dots,[2^{k-1},2^k),[2^k,n)\qquad (2^k \ge \frac n2)。
对于 x \in [2^k,n)，由以上引理可得 x 构成一个等差数列。
对于 x \in [2^{i-1},2^i)：
设 m 为 \max x，易知剩下的 x 也为 S_{1\dots m} 的 border。
而 x \ge \frac m2，故由上引理易知 x 构成一个等差数列。