各种 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\) 构成一个等差数列。