华理小男孩姚远数论概率论数学图论计算几何模板

"华理小男孩-姚远模板.pdf" 是一份关于编程竞赛和算法学习的文档，主要针对NOIP（全国青少年信息学奥林匹克联赛），ACM（国际大学生程序设计竞赛）以及NOI（全国青少年信息学奥林匹克竞赛）等比赛。这份文档由王亦凡、姚远和王泽宸等人共同编撰，包含了丰富的数论、概率论、数学、图论、计算几何和数据结构等领域的知识。 1. **数论**： - **指数降幂公式**：在计算大整数的幂时使用的高效算法。 - **威尔逊定理**：一个整数n是素数当且仅当(n-1)! ≡ -1 (mod n)。 - **费马小定理**：如果p是素数且a不是p的倍数，则a^(p-1) ≡ 1 (mod p)。 - **欧拉定理**：扩展了费马小定理，对于所有正整数a和n互质，a^φ(n) ≡ 1 (mod n)，其中φ(n)是欧拉函数。 - **质数表**：存储素数列表以快速查询。 - **素数函数**：用于判断一个数是否为素数的函数。 - **欧拉函数**：计算小于等于n且与n互质的正整数的数量。 - **莫比乌斯函数**：在数论中，莫比乌斯函数μ(n)是定义在正整数上的函数，用于研究数的因子。 - **逆元**：在模运算中，如果a和m互质，则存在一个b使得ab ≡ 1 (mod m)。 2. **概率论**： - **超几何分布**：描述不放回抽样中成功事件出现次数的概率分布。 3. **数学**： - **矩阵**：介绍了矩阵的类定义和高斯消元法，用于解决线性方程组。 - **整除与剩余**： - **扩展欧几里得逆元**：计算模意义下的乘法逆元。 - **中国剩余定理**：解决多个同余方程组的问题。 4. **图论**： - **最大团**：寻找图中最大的完全子图。 - **图的遍历和连通性**： - **割点和桥**：识别图中的关键节点和边，它们的删除会导致图的连通性改变。 - **双连通分量**：图中不能被任何一条边分割的子图。 - **强连通分量**：有向图中每个顶点都可以到达其他所有顶点的子图。 - **拓扑排序**：为有向无环图(DAG)的顶点排序。 - **2SAT**：解决满足二元逻辑表达式的布尔问题。 - **路径**： - **非递归欧拉回路**：找到图中包含所有边的路径。 - **匹配**： - **二分图最大匹配**：在二分图中寻找最大的匹配集。 - **二分图最优匹配**：考虑权值的二分图匹配问题。 - **树**： - **Prim算法**：用于构建最小生成树。 - **曼哈顿最小距离生成树**：构建最小生成树，同时考虑边的曼哈顿距离。 - **网络流**： - **最大流Dinic算法**：求解网络的最大流量。 - **最大流ISAP算法**：另一种求解最大流的方法。 - **费用流**：在网络流的基础上考虑每条边的费用。 - **无源无汇有容量下界网络的可行流**：在没有固定源和汇点的网络中寻找满足容量约束的流。 5. **计算几何**： - **判断凸包**：确定多边形是否为凸包。 - **判断线段是否相交**：检测两条线段是否在平面上相交。 - **求对称点求交点**：计算点的对称点或线段的交点。 - **终极模板**：可能是一套完整的计算几何问题解决方案。 6. **数据结构**： - **手写堆**：实现优先队列的堆数据结构。 - **左偏树**：一种自平衡二叉查找树。 - **两优先队列模拟堆**：结合两种优先级的堆实现。 - **线段树**：用于高效处理区间查询和更新的数据结构。 这份文档是为参加编程竞赛和深入学习算法的学生准备的宝贵资源，涵盖了从基础理论到高级算法的广泛内容。通过学习这些知识，学生可以提高解决问题的能力，并在竞赛中取得优异成绩。