一些小 trick
-
对两个集合的点两两连边时，除了线段树优化建图，还可以建一个虚点连接两个点集，把边数降成线性
-
有些数列的区间操作重复若干次后不再产生影响，比如区间开根，区间取模
-
树上点集 lca 等价于点集中 dfs 序最小、最大的点的 lca
-
\(\text{Hash}\) 思想配合随机判断一些东西是否相同
-
矩阵加速dp转移
-
普通图上dp：①用SPFA转移解决后效性问题；②记忆化搜索；③高斯消元
-
减少对无用状态的统计与枚举
-
在线复杂度较高时考虑离线怎么做
-
树上问题先考虑链和特殊情况怎么做
-
计数问题直接按题意统计复杂度较高时，考虑拆解成多部分的贡献，或单个元素对答案的贡献
-
树上背包 \(O(n^3)\) 优化至 \(O(n^2)\) -> 详解
-
线段树套分块优化时间空间
-
扩展域并查集判定二分图
-
范德蒙德卷积：
\[\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}
\]
- 来源：abc295E
In general, for a probability variable X that takes an integer value between 1 and M,
\[\text{(expected value of X)} = \sum_{i=1}^{m} (i \times \text{(probability that X = i)}) = \sum_{i=1}^m (\text{probability that} X \ge i) \]
- 枚举一个数 \(x\) 的二进制子集：
for(int S = x; S; S = (S-1)&x)