各种 trick 合集

各种 trick……

数据结构常见套路

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

莫比乌斯反演常见套路

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

一些公式

  • i=1ni=Cn+12=n(n+1)2\sum\limits_{i = 1}^n i = C_{n + 1}^2 = \dfrac {n (n + 1)} 2
  • i=1ni2=Cn+12+2Cn+13=n(n+1)(2n+1)6\sum\limits_{i = 1}^n i^2 = C_{n + 1}^2 + 2C_{n + 1}^3 = \dfrac {n (n + 1) (2n + 1)} 6
  • i=1ni3=Cn+12+6Cn+13+6Cn+14=n2(n+1)24\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