trick 小记

1. 数据范围可以 \(n^2\) 算法且不考虑顺序的情况下可以连续段 dp

2. 要仔细检查数组是否开小，线段树最少 4 倍，建边的数组看条数，一般情况下开 2m，注意看数据范围时 \(k\times 10^x\) 的形式，一数组两用直接开到 n

3. 维护线段最值用李超线段树，全局加是 \(O(log)\) ，动态开点常数小，涉及修改可以分块，区间加打 tag，散块暴力重构整块线段树

4. 只有 \(m\ and\ n=m\) 时，\(C_n^m\) 为奇数

5. 对于固定范围限制且贡献总量与范围无关的 dp 题，可以将每次移动范围变为移动起点，然后在不同起点赋初值，可以减少枚举范围的时间复杂度

6. 树上背包 \(O(n^2)\)

7. int 的上界范围是 \(2^{31}-1\)

8. 可以 \(O(n^3)\) 考虑区间 dp，正确的写法是枚举断点而不是扩展区间

9. 在一个数列的数确定时，只有一个中位数，记一下位置直接做

10. 对于一些高次计数，如果不易转移，可以先求每个答案的 k 次方和，二项式定理转移，然后用一些类似于插值的方法求系数得到答案

11. 对于一些求合法方案数的题目，其限制类似于不存在两个相邻的数满足某条件，考虑容斥，其基本形式为枚举每个位置是否合法，也就是这个式子：

\[ans=\sum (-1)^{|s|}f(s) \]

如果位置等价 那么显然只关心个数，如果不便于组合计数，但可以递推，可以发现，这个式子只和 \(|s|\) 的奇偶性有关，然后按奇数/偶数算方案数

12. 对于在坐标系上移动的问题，如果每次只能移到相邻的四个格子，那么可以转成切比雪夫，这样每次移动横纵坐标都会变化 1，操作就独立了

13. \(<iostream>\) 和 \(<bits/stdc++.h>\) 头文件占空间越 3MB

14. 求 n 个数，和不超过为 m 的方案数(>=1)，为 \(C_m^n\)，插板，最后一块板子后面为剩余值

15. 对于一些选数问题，要求每组个数之和，如果去掉任意个数都一定满足限制但只有选完能计入答案，可以钦定一个顺序，然后算不完全选完的方案数之和就是答案

16. 对于项数确定或差 1 的组合数求和，考虑递推式 \(C_i^j=C_{i-1}^{j}+C_{i-1}^{j-1}\)