各种 trick 合集

各种 trick……

数据结构常见套路

1. 去 log 的套路：
2. 可持久化。
3. 线段树上二分 / 树状数组上倍增。
4. 处理子树的套路：
5. 如果信息有区间减法 / 带修改，首选 DFS 序。
6. 线段树合并。

莫比乌斯反演常见套路

1. 如果题目的式子跟 gcd 有关，优先考虑莫反。
2. μ∗1=ϵ 比莫比乌斯反演公式快很多（指推导的时候）。
3. 如果有枚举约数的，尽量考虑把它提到式子最前面。
4. 对所有数对的 gcd 算一个式子时，考虑枚举 gcd 并算它贡献的次数。
5. 当 gcd(x,y)>1 时，μ(xy)=0。

一些公式

• n∑i=1i=C2n+1=n(n+1)2
• n∑i=1i2=C2n+1+2C3n+1=n(n+1)(2n+1)6
• n∑i=1i3=C2n+1+6C3n+1+6C4n+1=n2(n+1)24

某 border 结论证明

以下设 n=|S|。

弱周期引理

设 p,q 为 S 的周期，p+q≤n，则 gcd(p,q) 也是 S 的周期。

不妨设 p>q，则令 d=p−q。
对于 i−q>0，有 Si=Si−q=Si+p−q=Si+d。
对于 i+p≤n，有 Si=Si+p=Si+p−q=Si+d。
当 p+q≤n 时不存在 i 同时不满足以上两者。

引理

S 的所有长度不小于 n2 的 border 的长度为一个等差数列。

设 p 为 S 的最小周期，不妨设 p≤n2。
设 q 为 S 的一个周期，满足 q≤n2。
则由弱周期引理可知 gcd(p,q) 同为 S 的周期。
由上可知 gcd(p,q)≥p。
故显然 p∣q。

证明

字符串 S 的所有 border 按长度排序后可以划分为 O(logn) 段等差数列。

将 S 的 border 长度 x 分类为 [1,2),[2,4),…,[2k−1,2k),[2k,n)(2k≥n2)。

对于 x∈[2k,n)，由以上引理可得 x 构成一个等差数列。

对于 x∈[2i−1,2i)：
设 m 为 maxx，易知剩下的 x 也为 S1…m 的 border。
而 x≥m2，故由上引理易知 x 构成一个等差数列。