「Learning Notes」some tricks

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。
本文记录一些 OI 中常用的套路/技巧.

常见套路

  • 处理无根树问题时可以考虑定根.
  • 与度数相关的生成树问题,可以考虑 prefer 序列.

正难则反

有时候题目要求你多次做某种操作,但是单次操作维护较麻烦,则我们可以将所有操作都做完以后再倒着一个个撤销.
如: 给定一个图,多次进行删边及询问连通性两种操作;此时可以先将所有边都删去,再倒着将边加回来,用并查集维护连通性.
有时候需要求对于所有的 A ,满足要求的 B 的和。此时可以考虑枚举所有的 B ,计算其对每个 A 的贡献。

单位根反演(求和引理)

求和引理即:

\left[k | n\right]=\frac{1}{k}\sum_{i=0}^{k-1}\omega_{k}^{in}

在碰到如

\sum_{i=0}^{n}\binom{n}{i}a^{i}b^{n-i}\left[k | i\right]

形式的柿子时,可以用求和引理优化:

\begin{aligned} \sum_{i=0}^{n}\binom{n}{i}a^{i}b^{n-i}\left[k | i\right] &= \sum_{i=0}^{n}\binom{n}{i}a^{i}b^{n-i}\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij} \\ &= \frac{1}{k}\sum_{i=0}^{k-1}\sum_{j=0}^{n}\binom{n}{j}a^{j}b^{n-j}\omega_{k}^{ij} \\ &= \frac{1}{k}\sum_{i=0}^{k-1}\left(a\omega_{k}^{i}+b\right)^{n} \end{aligned}

「LOJ #6358」前夕