拓扑排序与关键路径
拓扑排序介绍拓扑排序是一种将一个有向无环图变成一个线性序列的算法。这个序列的要求是：每个顶点都出现了一次。对于一条边：$a \to b$，我们要求 $a$ 在 $b$ 的前面。实现找到入度为 $0$ 的点，输出。删除这个点和这个…
CATEGORY
信竞
这个分类下的文章与记录。56 篇内容
↗
模意义下的乘法逆元学习笔记
定义$a$ 的逆元写作 $a^{-1}$。我们定义 $a \times a^{-1} \equiv 1 \pmod p$。计算方法费马小定理知识链接欧拉定理 & 费马小定理 - OI Wiki (oi-wiki.org)费马小定…
Codeforces Round 923 A-E 题解
前言没时间打，所以 VP 了一下。[progressbar progress="71.428571428571428571428571428571" color="orange"]我的 VP 成绩：5 / 7[/progress…
树状数组
树状数组树状数组其实是一种针对于前缀和的优化。可以将区间查询和修改的复杂度讲从 $O(n)$ 降到 $O(\log n)$。算法主要思路正常的前缀和数组如果显示为一个树的话是这样的：也就是 $f_i$ 维护的区间是 $[1, i…
拓扑排序
前置知识DAG，是有向图（有向无环图）的简称。拓扑排序的定义如果 DAG 的一个遍历序列满足：每个点都访问了一遍。对于每个便，出发节点在目的地节点的前面输出。求拓扑排序定义 $d_i$ 为第 $i$ 个节点的入度。用邻接表储存一…