trick

· · 个人记录

连通块数等于点数减边数

Trie 上两串的 LCP 等于它们的 LCA

在并查集上维护子树和，可以支持单点修改权值

(\sum\limits_{i=1}^ka_i)^2=\sum\limits_{i=1}^k\sum\limits_{j=1}^ka_ia_j=\sum\limits_{i=1}^ka_i^2+2\sum\limits_{i=1}^k\sum\limits_{j=i+1}^ka_ia_j

光速幂可以只预处理一个 O(v\sqrt v) 的数组 f_{i,j}=i^j，因为另一个 (i^{\sqrt v})^j=f_{i^{\sqrt v},j}=f_{f_{i,\sqrt v},j}。

完全平方数，考虑唯一分解

一般情况下，高斯消元、矩阵求行列式消除第 i 列时，需要把一个第 i 列非 0 的行交换到第 i 行，

但某些时候（如需要维护一些额外信息时）可以视为，通过一些交换操作，

将这一第 i 列非 0 的行删除，然后插入到第 i 行。（求行列式时注意考虑乘上的系数）（来自 1.12 T2）

贪心策略不一定要直接求出最优方案，也可以求出一组合法方案后调整到最优方案。（3.30 T2）

如果需要对 01Trie 结构根号平衡，可以考虑 \sqrt V 叉 01Trie。

排列的逆序对数的奇偶性，与 n 减置换环个数的奇偶性相同。

每一类方案数的平方和 = 取出两个方案，且在同一类的方案数。

python 输出很长的 int 时，要加一句 sys.set_int_max_str_digits(1000000)

存在性二维数点不用真的二维数点，只需要在一维上维护另一维的最值。

暴算多个函数的卷积（多层枚举因数）比你想象的快。

cmath 里面 long double 系列函数比你想象的慢。

求 \min\limits_{a,b}(\max(a,b)) 或者 \max\limits_{a,b}(\min(a,b))，可以考虑分讨掉内层 \min，\max。

（\min 套 \min，\max 套 \max 可以直接扔掉内层 \min，\max）

生成函数题，可以求导找递推式。（CSP 第四次）

枚举每类元素放几个，可以暴力做 MSET（CSP 第六次）

静态区间单调栈可以用倍增处理

计数所有元素都满足条件的方案数，可以看成恰有 0 个元素不满足条件的方案数，然后容斥

统计合法区间数，有的时候可以不统计区间，比如说可以统计有多少值域区间对应合法的区间

总长为 m 的若干字符串在一个长为 n 的字符串中总共出现 O(n\sqrt m) 次。

李超树加一维偏序（比如给 n 个一次函数，每次问 [l,r] 内的一次函数与 x=k 的交点最值），

可以线段树维护凸包。

找两个点使得斜率最小：按 y 排序后只需考虑相邻的点。

可以用 GF 加一维限制：比如要求选了 k 条关键边的生成树个数，

可以令关建边权值为 x 跑矩阵树定理，提取 [x^k] 系数即可。

对每个点维护子树内部点对它的贡献和（类似 DSU on tree 干的事），如果贡献可差分的话，

可以 DFS 这个树，对每个点 u 维护 DFS 过的点对它的贡献和 s_u，

则它子树内的点对它的贡献和就是 DFS 出 u 时的 s_u 减 DFS 进 u 时的 s_u。

二分图最大权独立集可以转化成最大权闭合子图。

排列 DP，不仅可以每次插入一个最大值（n-1 阶排列 \to n 阶排列），

每次填入一个最大值（维护连续段），

还可以每次填入末尾的值，把之前大于等于其的值加一。

求一个区间使得价值最大，也可以考虑斜率优化/决策单调性优化。

区间最大前缀和/区间最大后缀和可以先求个全局前缀和/全局后缀和然后变成 RMQ。

长度为 n 的序列的所有子区间只有 O(nk) 种本质不同的前 k 大，证明考虑枚举第 k 大。

如果可以写出 BFS 暴力，可以考虑 A*。

可以用线性筛预处理模非质数的逆元。

统计交换两个数使得满足一定条件的方案数，也要记得考虑分治。

要哈希的串值域很大的话，base 取大点就行了。

一切哈希都要记得用双模，双模比较困难的话 ull 自然溢出也行，能不取模最好。

字母括号匹配问题（CSP 消消乐），可以考虑矩阵哈希。

要优化 f_{i-k}\to f_i 的转移，可以考虑按 k 分段，每次转移一段（nfls 10.29 T2）。

需要用点信息更新区间信息，或者区间信息更新点信息时，

如果用数据结构直接做比较困难，记得考虑数据结构优化建图。

建模题优化不动了，不妨换一种建模方法。

合并背包时如果不好卷积，可以考虑遍历其中一个背包的物品装进另一个（不一定需要启发式合并）。

整式递推，n 比 mod 大的话可以考虑找 f(n) 和 f(n+mod) 的关系。

线性 DP 比较困难的话，别忘了考虑区间 DP。

求一个式子 FWT 的结果，可以考虑直接代入定义式。

DP 答案很小时，别忘了考虑交换答案和状态。

【若干个不交简单环的并】与【所有简单环和非简单环】双射，

【所有简单环和非简单环】与【DFS 树上若干个返祖边形成的环的异或】双射。

不仅求最大解/最小解可以二分，求任意解也可以二分（每次确定其中一边一定有解）

一棵树至少有两个点权为 1 的点

在树上选出尽可能多条链/尽可能多个连通块，别忘了考虑从下往上贪心，能选了就选（CF1039D You Are Given a Tree）

给定 k，对于所有 i 连接 (i,i+k)，可以用萌萌哒。

只有删除/增大某个数和求最小值两个操作的话，在桶上维护一个指针就行了。

在考虑怎么去掉一个信息之前，先考虑不去掉它会不会影响答案。

括号序列问题，如果用栈匹配不好做的话，可以考虑用定义做（每次删两边的左右括号，或者分裂成两个合法的括号序列）， 另外别忘了考虑括号树。 如果需要容斥，推 GF 时可以带着容斥系数。 集合幂级数半在线卷积，可以把下标按 popcount 分类，然后依次求解每一类。（实际上是对 popcount 加了一个类似子集卷积的限制） 排列双射二分图匹配，参考积和式。 短 vector 常数比数组大很多，长 vector 常数和数组差不多 n 小于等于三十四十五十：考虑 n^5/n^6/分拆数/meet in the middle 等 函数复合，考虑扫描线 树套树不一定不能区间修改，可以考虑标记永久化 DFS 到一个点时，不可能已经开始 DFS 的点：子树 DFS 到一个点时，不可能已经结束 DFS 的点：子树、祖先 DFS 出一个点时，不可能已经开始 DFS 的点：无 DFS 出一个点时，不可能已经结束 DFS 的点：祖先 总之就是别忘了想括号序 $T(n,k)=f(n)+T(n,k-1)+T(n/2,k-1)

则

T(n,k)=O(kf(n))

可以分析一些分治的复杂度，一般 k=O(\log n)。

BSGS 多组询问，竟然可以调块长平衡复杂度的，，，

冒泡排序，可以在 x_i=\sum\limits_{j<i}[a_j>a_i] 上考虑，每次把大于 0 的位置减一，然后向左平移一位。

看起来不好解决的限制，不一定要转化成别的限制，也不一定要压进 DP 状态，可以考虑保证所有状态满足这个限制。12.24 T4

\min(n,m)\le\sqrt{nm},\min(n,m)\le(n+m)/2

所有子树的 DFS 序区间不会部分相交

对于区间 DP 的决策单调性优化，一行/一列的决策点是有单调性的，可以二分队列来避免均摊复杂度

线段相交其实是一维偏序，只需要对每条线段找出其包含的所有左端点

容量上限为 m 的树形背包是 O(nm) 的。

字符集较大时建立 AC 自动机可以直接暴跳 fail 树，复杂度是 \sum|s_i| 的。

连通块无环：森林，连通块最多一个环：基环树森林，连通块内环不交：沙漠

基环树判断方法：定向后每个点出/入度都为 1

最小值最大/最大值最小不一定是二分

斜率相关可以想想 KTT，这玩意至少强于李超树

时刻记住 \sum iF(i)=\sum F(\ge i)，F(i) 算不了的时候这个比较自然，F(i) 能算的时候也要想想这个

要判存在性，即使很好转计数，也先想想能不能不转计数

看起来规约 OV 的东西可以考虑 FWT

最优化也可以考虑转计数

扫描线题难以优化时，可以尝试把扫右端点改成扫左端点，或者反过来

看到曼哈顿距离/切比雪夫距离先想想能不能转成另一个

记得考虑期望线性性 看到平均值就要想分数规划，即使是无限长序列的平均值 树上有后效性转移，考虑树上高斯消元 大函数别加 inline，会慢 考虑决策单调性的时候别忘了斜率优化 带后缀最值的转移有时可以根据性质去掉后缀最值（nfls 2.14 T1 2.17 T1） **计数题记得考虑组合意义。** 图论建模： 1 对 1 / 1 对 k / 1 对 a[i]（例如：每个时刻最多进行 1/k/a[i] 个操作）/ 棋盘黑白染色（例如：骨牌，放马）：二分图（别忘了 hall 定理） 二选一/选或不选，加限制（例如：文理分班）：最小割 选物品有前置条件（例如：01 保序回归）：最大权闭合子图 线性规划模型（例如：志愿者招募）：费用流/费用流对偶 二选一/多选一（拆变量）构造，A 怎么样则 B 怎么样（例如：草莓城市）：2-SAT 别忘了考虑模拟费用流 别忘了考虑经典模型的对偶（最大匹配对偶最小点覆盖，最大权匹配对偶最小顶标和） 瓶颈比 n^2 大的话，可以用插值去掉瓶颈上的一维卷积 **二维优化建图，可以用主席树，不一定要树套树 / KDT** **并查集点对区间连边，可以直接均摊复杂度** **把一个题转化成感觉不可做的形式时，一定是没有发现某些性质** **线段树可以维护 DFS 序区间根链并**