值得一记的小技巧

cainiaoshanglu · 2023-07-10 14:40:57 · 个人记录

个人向杂记

0.在机房做题时不能唱歌/狗叫/说批话，不然会 G。

1.无向图统计与边数有关信息： 考虑让每条边从度数较小者连向较大者，此时每个点的边数不超过 \sqrt m：原图中度数小于 \sqrt m 者自不必说，而原图中大于者必然连向度数更大者，注意到总边数限制，最多连 \sqrt m 条。这一技巧可用于统计三/四元环数量等问题。

2.DFS 树： 无向图 DFS 树同层节点不会存在连边。构造题中会十分有用的性质。

3.求最优 k 个方案：考虑将所有合法方案组成一棵以最优方案为根的外向树，其中每条边必须从较优者指向较劣者。这样最优k个方案必然是一个包含根的连通块，通过 priority_queue 可以快速得到。注意在构造过程中保持每个方案的转移数量为 O(1) 级别。

4.hash：哈希时可以对于每个字符进行一定的变换（比如 x*x+7)，防止被别有用心的出题人卡掉。同时考虑更大的底数和随机出来的模数。

5.求 n 个数的逆元：可以先累乘，对于最后一个数 \log 求逆元，然后乘回去，从而得到逆元的前缀积，再算一次就可以实现 O(1) 解决。

6.n\times n 循环矩阵求行列式：将第一行拿出来当做一个 n-1 次多项式的各项系数，对这个多项式求在 n 次单位根上的点值，其累乘积就是行列式。

7.排列问题：通常有两种解决方式，相对位置或相对值 dp，或容斥。一般都需要 dp，大概率可以前缀和或者NTT优化。

8.构造两个状态之间的转移路径：可以构造一个易于到达的中间状态，然后从两侧分别到达之，尝试合并贡献。注意后半部分需要维护反向和。

9.随机序列的 LIS 是 O(\sqrt n) 级别的。

10.图论等式：最大流等于最小割，最长反链等于最小链覆盖 (Dilworth)，二分图最大匹配等于最小点覆盖 (König)。

11.若求解结果为某低次多项式形式，可以直接上拉格朗日插值。经典案例为扩散的正方形面积并。

12.dp 题目没有优化思路的时候可以尝试把转移放到单个点上而非枚举区间。常见手段包括进行组合转化。

13.最大权闭合子图可以通过最小割解决。将原图所有边流量上限设为 +\inf，将正权点与源点相连，负权点与汇点相连，上限为权值绝对值。所有正权之和减去最小割即为结果。

14.k-nim问题（若干堆石子，每个人可以从中 1 ~ k 堆取一个石子，不能取者败）先手必败当且仅当存在 i 使得各堆石子数的第 i 个二进制位上 1 的数量为 k+1 倍数。

15.短多项式求幂可以转化成低次递推：

16.边权如果涉及取模可以尝试将点放在环上（ABC232G）。

17.区间线性基可以对于每个点求类似单调栈的结构：对于每个点记录当前值加入的的位置（时间戳），每次加入新点考虑当前位置的时间戳是否早于当前值，如果是则交换，然后按照正常流程继续向下即可，每次取出右端点时间戳早于左端点的各项值即可。

18.五边形数定理:

在 n 以内只有 O(\sqrt n) 项非 0.

19.拓展Cayley定理：如果有 n 棵树，大小分别为 x_{1...n}，将它们连接为一棵树的方案数为 (\sum x_i)^{n-2}\prod x_i.

20.本质不同回文子串是 O(n) 的，且每个前缀至多有一个后缀为之中之一。

21.需要节省空间可以把多个变量压在一起，写成一个结构体:

struct Node {
    ull mx : 18, ls : 23, rs : 23; 
};

上述结构体只占据8字节空间。

22.一个 n 阶排列的LIS和LDS至少有一个长度大于 \sqrt n.

23.巴雷特约减快速取模（Barrett reduction）：

const __int128_t p=(__int128_t(1)<<64)/md;
unsigned long long Qmod(unsigned long long k){
    return k-((k*p)>>64)*md;
}

在 k\lt 2^{64} 内有效，但可能返回 k \bmod md 或者 k \bmod md + md.

24.区间本质不同元素数量可以转化为二维数点，对于每个数记录其与其值相同的前驱 prv_i，则所统计为 l \leq i \leq r, prv_i < l。

25.对于两个字符串 s,t 而言，st 与 ts 的大小关系与 s^{\infty} 与 t^{\infty} 的关系相同。换言之，这两种关系等价且都构成在字符串集上的全序。

26.在 n \times n 的网格图上任意选取 n 个点，其组成的凸包/凸壳的点数是 O(n^{2/3}) 级别的。

27.(min/max)= 使用专门函数优化显著。

28.将一颗带点权树的权值拍到dfn序上，则该序列的带权中点必然在原树的重心子树之中。

29.对于一些选出最优边集的问题，若该边集在最优时为森林，可以通过给每个点随机 0/1 颜色转化为二分图上的问题（森林是二分图）。注意分析正确率。

30.一个 n*m 01矩阵里面的极大全1连续子矩阵的数目是 O(nm) 的，通过枚举起始行以及约束列可以 O(nm) 找到。

31.考虑区间问题时，可以考虑包含和相交的情况，如果其中一个是平凡的则可转化解决。

32.通过 Meet in the middle 可以实现 O(2^{n/2}) 统计子团。结合 (1) 可以做到 O(\sqrt m2^{\sqrt {m/2}}) ，实测可以通过 m=1000.

33.半平面查询随机数据有简单实现可以做到 O(n^{1.5})：考虑将两维根号分块，则每个方格期望有 O(1) 个点，每次查询时可以对于每个线经过的方格暴力计算，而其余部分可以拆成 O(\sqrt n) 个前缀和查询。

34.平面上的四联通路径计数：一个点到到一个矩形可以通过二维前缀和转化为一个点到四个点的方案数。

35.哈夫曼树是所有类似的树中使得 \sum a_i2^{dpt_i} 最小的，故其深度是 O(\log n+\log V) 的。

36.对于一棵树上的任意一点 u 而言，称距离它最远的点为“最远点”，则任取一条直径，直径端点中必有一个为“最远点”。

37.树的拓扑序计数是：

也可写作：

其中 v_i 为 u 的儿子。

38.考虑网格偏序路径问题（只能往上或者往右）时，如果存在限制形如：不能碰到直线 y=x+l 和 y=x+r，要从 (0,0) 到达 (n,m)，总方案可以通过反射容斥得到：

39.对于一个集合求线性基可以随机选出 \log qV+\epsilon 个子集，将他们的异或和组成线性基，可以认为是原集合的线性基。正确性分析可以见 zky 论文。

40.海森堡矩阵（上三角和主对角线下一的对角线有值）求行列式：每一个置换环必然形如一个自环或者 i \to j \to j+1 \to j+2 \to ...\to i，是一个区间的形式，而且其逆序对仅在环内部产生。

41.统计一个图的匹配可以考虑将点两两分组视作大点，则匹配可以看做大点形成的环和链，实现 2^{n/2}poly(n) 的复杂度。

42.给定 r，x^2+y^2=r^2 的正整数解数量是 4\prod (2\beta_i+1)，其中 r=2^\alpha\prod p_i^{\beta_i}\prod q_i^{\gamma_i}，而 p_i,q_i 分别为 4k+1,4k+3 型质数。

43.对于一个排列 f_i，令:

显然：

而且对于所有满足上述条件的 g 都存在一个对应的 f. 每次冒泡排序遍历会导致所有不为 0 的 g 值减 1，因此冒泡排序遍历次数为 \max_{i=1}^n g_i.

44.求对于一个数的大量的取模乘法时，可以先求出其浮点数逆元，然后转化为乘法，注意正好整除时的精度问题需要 +eps.

45.对于 k 阶线性递推 b，可以通过 a_{n-k+1} \sim a_n 线性推出 b_n，其中 a 为初值为 0,...,1 的同系数线性递推。

46.对 n 取模的斐波那契数列的循环节是 O(n) 的。

47.生成随机数使用以下模板：

int seed=998244353;
int rnd(){
    seed^=(seed<<5);
    seed^=(seed>>11);
    seed^=(seed<<7);
    return seed;
}

可以生成高质量随机数。注意不可以改变顺序或者运算。

48.指令相关：Linux 下 \time -v ./sth 可以测试某个程序的运行时间，内存和栈空间。从system 函数运行的 fc 指令在找不到差异时会返回 0。、

49.对于 n 阶矩阵 M 而言，\det M \bmod p 非零的 M 数量是 \prod_{i=0}^{n-1} (p^n-p^i)。（sk 贴贴！）

50.数学公式大集合：https://blog.shahjalalshohag.com/equation-list/

51.（QOJ 9047）对于带权二分图匹配恰好 K 个的问题，只有每个点最大 K 条边有用，此时每一条边只与 O(K) 条边相邻，故只需要取出其中最大 O(K^2) 条边即可，此时点数和边数均为 O(K^2)。

52.牛顿多项式的性质：假如将 F(x) 写成