想着写点什么东西，就是说，不会被归入知识点，却又感觉很常用的东西。
哦我懂了，通常来说我们管这个叫 trick。
先记一记自己遇到过的。
DS
不强制在线复杂度不依赖均摊的可持久化数据结构 \(\to\) DAG 上直接模拟。
猜猜这里内涵的是哪个名字叫并查集的小朋友
哦哦更新了，还有你，线段树合并
只要求在最新版本上修改和查询所有版本的可持久化数组可以在
vector上二分，又唤部分可持久化。在同时可以使用线段树合并和主席树解决的问题中，选前者。
问就是跑不满
数学
先整点若智的视力问题。虽然我在数学方面跟若智也没差太多了。
\(\{1,1,2,3,5,8,\cdots\}\) 是斐波那契，兔子生兔子那个；矩阵可以优化；生成函数可以找通项；
\(\{1, 1, 2, 5, 14, 42, 132, 429, 1430,\cdots\}\) 是 Catalan，走网格不能穿过对角线 / 构造二叉树方案数 / 一群人买电影票那个。有组合求法 \({2n\choose n} - {2n \choose n - 1}\)；生成函数还是可以找通项；
\(\{3, 7, 6, 15, 25, 10, 31, 90, 65, 15, 63, 301, 350, 140, 21, 127, 966,\cdots\}\)，中间插着 一堆 \(1\) 我写不下了所以删了，是展开了的第二类斯特林数三角形，把 \(n\) 个不同球，不空放，放到 \(k\) 个相同盒子的方案数，有递推式 \(S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)\) 和二项式反演出来的通项 \(S(n,m)=\sum\limits_{i=0}^m\dfrac {(-1)^{m-i}\cdot i^n}{i!\cdot (m-i)!}\)。多项式可以 \(n\log\) 算同一行 / 列，方法不太一样。
\(O(n)\) 求 \(1\sim n\) 模 \(p\) 意义下的逆元：
\[ \because p=\left\lfloor \dfrac pi\right\rfloor\times i+p\bmod i\\ \therefore 0\equiv\left\lfloor \dfrac pi\right\rfloor\times i+p\bmod i\pmod p\\ 0\equiv\left\lfloor \dfrac pi\right\rfloor+(p\bmod i)\times i^{-1}\pmod p\\ p-\left\lfloor \dfrac pi\right\rfloor\equiv(p\bmod i)\times i^{-1}\pmod p\\ (p-\left\lfloor \dfrac pi\right\rfloor)\times (p\bmod i)^{-1}\equiv i^{-1}\pmod p \] 然后我们又知道如果从前往后求逆元，\((p\bmod i)^{-1}\) 肯定会在 \(i^{-1}\) 前求得，所以一遍扫过来就行了。注意要从 \(2\) 开始求。
如果要求 \(1\sim n\) 阶乘的逆元，只需要把刚刚求得的答案前缀积一下就行。
\(O(n)\) 求任意 \(n\) 个数的逆元：
inv[0] = 1; for (int i = 1; i <= n; ++i) inv[i] = inv[i - 1] * a[i]; inv[n] = qkp(inv[n], mod - 2); for (int i = n; i; --i) { int t = inv[i - 1]; inv[i - 1] = inv[i] * a[i] % mod; inv[i] = inv[i] * t % mod; }
图论
比如有对图中边权的更新。像是让你求某某的最小，然后更新操作是减小某个边权。
这个时候我们就会发现改边不太现实，可以直接加边，因为保留原来那条更大的边不会影响答案。
题不知道。
有环图上的 DP，通常来说可以根据状态转移方程的形式找到环上的「根源」，即不由任何环上节点转移得到。
无视根源在环上的前驱边就可以用类拓扑的方式转移。
Goto solu to 商人。
关于树的直径：
树的半径（即 \(\min\limits_x\{\max\limits_y dis(x, y)\}\)）的一端一定在直径上，且在直径中间。
如果不带权的话就是直径长度的一半
不然为啥叫半径。如果知道一坨连通块内的直径是 \(x\to y\)，另一坨是 \(a\to b\)，那么两个合并起来的直径一定是 \(\{x,y,a,b\}\) 里的 \(C_4^2\)。
以及树上的连通块是树
动态维护树的直径（比如修改叶子的边权，这里是为了保证单点修改）：
用上面提到的方法，线段树维护一段连续欧拉序内（不用 DFS 序是为了保证联通）的直径和两个端点，然后求 dis 再合并。为了快点儿我们在顺势欧拉序上 st 表来查 LCA 即可 \(n\log\) 地解决问题。
奇奇怪怪的优化建图：
通用的是 \(n\log\) 线段树，目前还见到过前缀和优化建图（前提是每条边都指向某个前缀区间，与线段树优化建图相比的优势是虚点数为 \(O(n)\)，eg）。
DP
用计数 DP 代替你那又臭又长还调不出来的该死的大容斥。
碰到了「起点状态到终点状态，中间不能经过一些非法状态的方案数」，可以用 \(f_i\) 表示从起点，不经过 \(1\sim i-1\) 的非法状态，到达非法状态 \(i\) 的方案数，最后将终点状态也视为一个非法状态并 DP 即可。
要求字典序大于 / 小于给定值的方案数，考虑使用 \(f_i\) 表示 \(1\sim i\) 全部和给定值相同，\(i+1\) 大于 / 小于给定值，后面乱搞的情况总数。
Goto 冒泡排序。
求方案数，如果用通常的「考虑满足条件的情况并转移」，就必须能够简单地对条件进行判定。
如果这一点做不到，可以考虑从最简单或最极限情况出发 构造 出一般情况，并计算相应的方案数。
Goto solu to 染色。
如果有转移会有后效性不妨考虑是否有前效性然后逆序 DP。
比如题目让我们求最小字典序。你只知道最后一个字符肯定不能推断出谁的字典序最小，但如果你知道最开头一个字符，并保证从后往前填表的每一步都走的最小就可以。
Goto solu to 匹配数。
状态拆分技巧。比如状态 ABC 不一定要从状态 A、状态 B、状态 C 分别 \(O(m)\) 的转移，而可以从 A 和 BC 以 \(O(1)\) 完成转移。
Goto solu to 单词。
有结论：一个长度为 \(n\) 的 \(1/-1\) 随机序列的前缀和离 \(0\) 的距离期望不超过 \(\sqrt n\)。
故胡乱拓展一下，在保证值域内分布均匀的整数域内背包，在
random_shuffle后实际最大状态不太会超过 \(\sqrt V\)。因为这个是由一个科什么什么定理推来的中间很松的结论，所以运气比较好的时候甚至不会超过 \(\log v\)。
哈希
用哈希解决，呃，怎么概括呢，比如区间计数，其中合法区间的左右端点对应着一种转化后的「全等」关系……？
Goto Three Occurrence。
xor hash
使用于异或判断次数奇偶性 / 元素存在性的哈希。
我们知道，区间里每个值出现次数都是偶数的必要不充分条件是区间异或起来为 \(0\)。之所以不充分是因为存在类似 \(1\oplus 2\oplus 3=0\) 的情况。
然后怎么让他变成充要的呢，哎，我们把每个数都给他哈希成一个随机大数（比如 ull），这样冲突的概率就会变成 \(2^{-64}\)。
Goto 牛客题，NOI2024 D1T1。
杂七杂八
对于悬线法：可以顺带维护一些东西。
具体可维护的东西和倍增差不多吧，还是比单调栈泛用性大很多的。是单调栈 / 单调栈上二分的 \(O(n)\) 平替。
但事实上可以用笛卡尔树完美替代 /擦汗
不过肯定悬线是好写很多的。
Goto solu to 情景剧。
关于 LIS 一类的，要求一个下标在序列 LIS 中（显然有多种 LIS 的方案）的出现次数。
这个时候分别统计以其结尾和开头的 LIS 长度与次数，如果加起来是序列 LIS 的长度，那么次数相乘就是答案。
\(k\) 个「二者至少选其一」形式的限制，要求选的尽可能少，使用 \(2^k\) 枚举后取并集代替你那脑子被电灯泡撞了才能想出来的 \(3^k\) 枚举。