矩阵树定理 定义 邻接矩阵：\(A=(a_{ij})\)，其中 \(a_{ij}\) 表示 \(i\) 到 \(j\) 有几条边相连。 度数矩阵：\(C=(c_{ij})\)，为对角矩阵，其中 \(c_{ii}\) 表示 \(i\) 的度数。 基尔霍夫矩阵：\(D=C-A\)。 余子式：\(M_{ij}\) 表示去掉第 \(i\) 行第 \(j\) 列后得到矩阵的行列式。 ...

就是把字符串转变成一个树，每个节点连接下一个字符，用空间换时间。 对于区分大小写或不区分的题目，只需要改变 ch[][26] 的值就行了。 ch[u][x] 表示 u 节点（标号决定）下一个 x 字符节点的标号。 如果题目让记录附加值，那就用 val[] 在插入时记录一下就好了。 1234567891011121314151617181920212223242526272829...

主定理（Master Theorem）通常是指在算法分析领域中的一个定理，特别是用于分析递归算法的时间复杂度。 时间复杂度相关定义 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。其原理在于，将计算机的每种基本运算（如加减乘除）所需的时间视为常数，然后考察一个算法调用了多大量级的基本运算。时间复杂度常用大 \(O\) 符号...

“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”——《孙子算经》 中国剩余定理 即求多个同余方程的解。 举个栗子。求一个数x，使得： \[\begin{cases} x≡2\pmod 3\\ x≡3\pmod 5\\ x≡2\pmod {11}\end{cases}\] 设 \(M=3*5*11=165\), \(a1=3\), \(a2=5\),...

二项式反演 \[ \begin{aligned} g_n=\sum_{i=0}^n(-1)^i\binom ni f_i\Leftrightarrow f_n=\sum_{i=0}^n(-1)^i\binom ni g_i\\ g_n=\sum_{i=0}^n\binom ni f_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom...

前言 前几天考试了发现这个东西完全不会欸……学了又忘真是讨厌至极 QAQ 所以又在网上找着看了看写一篇博客备忘。 学习笔记真的很有用！ 分层图 这个很容易理解，来源就是在一些最短路的问题上题目又加了比如说主角可以用传送宝石进行折跃之类的问题（针对），即可以选择k条边把这些边的边权变为零。 怎么样解决呢？可以在原图的基础上多复制k个相同的图，并用k条边把图之间的边用0边权边相连。就...

问题描述 有 \(n\) 个物品，每种物品两个权值 \(a_i\)，\(b_i\)，求一组 \(w_i\in\{0,1\}\)，使得 \[ \frac{\sum_{i=1}^n w_i\cdot a_i}{\sum_{i=1}^n w_i\cdot b_i} \] 最大（或最小）。 有可能包含其他限制。 二分法 显然答案是单调的。对一个答案 \(mid\)，有 \[ \...

就是三倍经验 题意 维护一个序列，每次修改后求出当前序列逆序对个数。 思路 题目让我们求出 \[ \sum_{i=1}^n\sum_{j=i+1}^n[a_i>a_j] \] 也就是让我们求出满足 \[ pos_i<pos_j\&\&a_i>a_j \] 的点对数量。 对于不修改的情况，这显然是一个三维偏序问题，用树状数组或归并处理都可以。...

无用的文字 又是一篇笔记，因为不做题的话太容易忘了啊啊啊QAQ看到一个题目知道用什么算法做但就是想不出来的感觉太难受了…… 二分图最大匹配 二分图 二分图是指可以被分为两个不相交点子集的图，其中相同点集内无连边。 匈牙利算法 匈牙利算法是用来寻找最大匹配的一个算法。 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。 增广路：从一个未匹...

算法描述 基数排序（又叫做桶排序）是一种非比较排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。 基数排序的步骤如下： 找出最大数，确定位数。 确定每个位数的范围，并统计每个数字在每个位数上的数量。 位数从低到高按每个位数从小到大进行排序。 输出排序后的数组。 123456789101112131415161718192021222324252...