- \(\sum_{i=1}^{n}\sum_{j=i+1}^{n}dep_{LCA_(i,j)}\)
可转化为：依次统计从 根节点 到 \(i\)
的边权和，统计完后将 根节点 到 \(i\)
的所有边的边权的倍数增加 \(1\)。
- \(f_{m+n}=f_{m-1}\times f_{n}+f_{m}\times
f_{n+1}\)，\(f_{i}\) 表示
斐波那契数列 的第 \(i\) 项。
- 假设当前有 \(n\)
个整数，时刻更改一个数的值，维护乘积，要取模。可以表示为 \(x\times 0^y\)，多一个 \(0\) 就将 \(y\) 增加 \(1\)，少一个 \(0\) 就减少 \(1\)。\(x\)
为其他数的乘积。
- 设 \(G\) 是 \(n \geq 3\) 阶 \(m\) 条边的简单平面图，则 \(m\leq 3n-6\)。
- 逆序对可以转化为二维平面上的点对。对于求一个排列的所有子区间的逆序对数量的最大值，可以转化为扫描线在
\(O(n\log n)\)
的时间内求出。具体的，求出前缀最大值和后缀最小值，然后二分查找每个点能产生贡献的范围，转化为若干矩形，区间加，全局
\(\max\) 即可。
- 若 \(ab=n^2,bc=m^2,n,m\in \mathbb
N\) 根据唯一分解定理有 \(ac=k^2,k\in
\mathbb N\)。
- 阶的求法：先求出 \(\varphi(p)\)，然后分解质因数，依次尝试去掉每个质因子，最后剩下的数就是阶。时间复杂度
\(O(log^2p)\)。
- 现有多条路径，每条路径有一个权值，再给定一条路径，问与给定路径有交的路径的权值和。一条路径上点数减去边数正好是
\(1\)。因此对于一条路径，我们将这条路径上的点权增加
\(v\)，将边权减少 \(v\)。对于给定路径求路径上点权和加边权和即是答案。可以使用
DFS 序+BIT 实现，当然也可以树剖。
- 矩乘优化 DP 通常是一个向量乘上一个矩阵，时间复杂度是 \(O(n^3\log n)\) 的，但假如需要算 \(m\) 次，时间复杂度变为 \(O(n^3m\log
n)\)，有时候无法接受，此时可以预处理转移矩阵的 \(2\)
的整数次幂的幂，并且计算时用向量乘以矩阵，此时时间复杂度变为 \(O(n^3\log n+n^2m\log n)\)。
- 二分图上博弈，先手必胜当且仅当起点一定在二分图的最大匹配上（需要在所有可能的最大匹配方案上）。
Trick 合集
2025/3/12
OI