各种 trick 合集

各种 trick……

数据结构常见套路

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

莫比乌斯反演常见套路

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