2023年7月30日发(作者：)

ACM-ICPC模板整理备注其⼀：正在整理中，内容不全，部分代码测试次数较少或还未在OJ上尝试，可能会有代码不健全的情况发⽣。备注其⼆：部分图⽚来⾃百度百科、wiki百科。备注其三：CSDN⼀天只能上传⼗篇只能慢慢传了。备注其四：中间修改了（咕咕咕）了好长时间，⽬录⼜发⽣了⼀些变化。。。

⽬录扩展欧⼏⾥得递归实现递推实现得到(0, mod]之间最⼩同余整数得到[-mod, 0)之间最⼤同余整数⼀元线性同余⽅程(Linear Congruence Equation)多元⼀次不定⽅程（丢番图⽅程）求解中国剩余定理 (Chinese Remander Theorem, CRT)扩展中国剩余定理 (扩展CRT)勾股数组本源勾股数组枚举⽅法（其⼀）本源勾股数组枚举⽅法（其⼆）相关性质寻找最⼩数为奇数的勾股数组的快速⽅法已知⼀条直⾓边构造勾股数组费马⼤定理 (Le dernier théorème de Fermat)费马⼩定理 (Fermat's little theorem)欧拉定理扩展欧拉定理卡迈克尔函数卡迈克尔数取模逆元（模反元素）互素情形⾮互素情形欧拉线性筛素数法威尔逊定理最⼩质因⼦欧拉线性筛打表实现Miller-Rabin Primality Test(⽶勒-罗宾随机素性测试)静态素数证据表实现（⾮随机数实现）使⽤Java⼤数类判断素数欧拉函数质因数分解实现（适⽤于单次求值）打表实现欧拉函数的性质σ因数和函数整数分拆杜教筛斐波那契数列定义前缀和性质⼴义斐波那契数列 (Generalizations of Fibonacci numbers)卢卡斯数列卢卡斯定理推论Numerical Methods（数值⽅法）表达式重构解决有效数字缺失问题⾼精度平⽅根⽜顿迭代法实现Gauss(⾼斯)消元法整数快速模幂法（逐次平⽅法）三分法模拟退⽕康托展开Catalan Number (卡特兰数)通项公式递推关系渐进关系相关问题卡特兰数扩展问题字典序下⼀个排列STL内置函数范德蒙恒等式推论杨辉恒等式纵向递推式横向递推式对称表达式组合聚合性恒等式推论⼆项式定理推论多重集合排列数⽆限多重集有限多重集多重集合组合数⽆限多重集有限多重集错排公式Data Structure（数据结构）有向树Segment Tree (线段树)K-D Tree（K维树）Binary Indexed Tree（Fenwick Tree，树状数组）⼆维树状数组【待补充初始化函数】AVL TreeRed Black Tree（红⿊树）Trie (字典树)Static Naïve implementation(静态数组实现)Map and Vector implementation(STL实现)Class Implementation Using map and vectorInterval Tree(区间树)Chtholly Tree(珂朵莉树)【简化版区间树+STL map】Naïve Implementation(简单实现)Efficient Implementation(⾼效实现)树链剖分块状链表舞蹈链 (DLX, Dancing Links)可持久化线段树可持久化块状数组可持久化字典树可持久化平衡树Graph (图)Topological sort(拓扑排序)最⼩字典序拓扑排序Floyd判圈算法 (Floyd Cycle Detection Algorithm)差分约束系统【待验证】仙⼈掌图⽆权⼆分图匹配匈⽛利算法 (Hungary Algorithm)Hopcroft-Karp算法⼆分图最⼤独⽴集与最⼤团带权⼆分图匹配EK算法Shortest Path(最短路)Dijkstra’s algorithmSPFA【注：计数部分有待测试】Floyd-Warshall Algorithm次短路改版Dijkstra algorithm解决⽹络流最⼤流最⼩割Tree（树）Euler tour（树的欧拉遍历序列）完全⼆叉树判断斯坦纳树最⼩⽣成树String（字符串）Levenshtein距离（编辑距离）LCS（最长公共⼦序列）距离Jaro距离汉明距离Damerau-Levenshtein距离Brute Force Pattern Search（暴⼒匹配）KMP (Knuth Morris Pratt) Pattern Searching拼接串（KMP应⽤）Manacher Algorithm(线性最长回⽂⼦串算法)Z algorithm【待测试】Rabin-Karp Algorithm（字符串Hash）ELFHashPattern Searching in Finite Automata(有限状态⾃动机模式匹配)Boyer Moore Algorithm（BM算法）Bad Character Heuristic implementation (occurrence heuristic)Good Suffix Heuristic implementation (match heuristic)Using both bad and good heuristic(同时使⽤上⾯两种信息)Boyer-Moore-Galil implementation(最差时具有线性复杂度)Aho-Corasick Algorithm(AC⾃动机)Trie图Fail树 (Fail Tree)后缀数组 (Suffix Array)倍增构造法DC3线性构造法正则表达式【部分⽐赛环境⽆法使⽤】常⽤表达式查询表C语⾔中使⽤正则表达式⾼精度BigInteger（⾼精度整数）C++版本Java版本常⽤⽅法说明BigDecimal（⾼精度⼩数）C++版本Java版本常⽤⽅法说明分数类复数类选择⼆类划分（Partition）【待测试】median-of-three版本指定枢轴值版本区间k⼩/⼤元排序解决使⽤⼩/⼤顶堆解决带旋转的Treap解法分块法划分树解法主席树解法BFPRT算法（中位数之中位数算法, Median of medians）整体⼆分CDQ分治查找⼆分法lower bound implementationupper bound implementation搜索DFSBFS同权值结点⼀次性出队的⽅法双向BFSmeet-in-medianA* Algorithm(A*算法)IDA (Iterative Deeping A)IDA* (Iterative Deeping A*)动态规划 (Dynamic Programming)最长上升⼦序列 (Longest Increasing Sequence, LIS)最⼤和值最长上升⼦序列 (Maximum Sum Increasing Subsequence, MSIS)最长下降⼦序列 (Longest Decreasing Sequence, LDS)最长⾮连续回⽂⼦序列 (Longest Palindrome Substring, LPS)最长公共⼦序列 (Longest Common Subsequence, LCS)最长重复⼦序列 (Longest Repeated Subsequence, LRS)最短编辑距离 (Shortest Edit Distance)最⼤连续⼦段和 (Maximum Subarray Sum, MSS)0/1 背包谜题与技巧 (Puzzles and Tricks)投掷鸡蛋问题 (Dropping Egg Puzzle)⾻牌覆盖问题 (Tiling Problem)n * 2地图⽤1 * 2⾻牌覆盖（可旋转）n * 3地图⽤1 * 2⾻牌覆盖（可旋转）n * 2地图⽤1 * 2⾻牌和2 * 2⾻牌覆盖（可旋转）n * 4地图⽤1 * 2⾻牌覆盖（可旋转）n * m地图⽤1 * 2⾻牌覆盖（可旋转）n * m地图⽤1 * 2和1 * 1⾻牌覆盖（可旋转）约瑟夫问题 (Josephus problem)扩展约瑟夫问题 (Enhanced Josephus problem)阶乘因数计数差分前缀和与后缀和⼀维前缀和与后缀和⼆维前缀和与后缀和n维前缀和与后缀和树形前缀和尺取法莫队算法 (Mo’s Algorithm)井字棋博弈 (Tic-Tac-Toe Game)博弈MiniMax算法（极⼩化极⼤化算法，MM算法）α-β剪枝策梅洛定理 (Zermelo's theorem)Nim游戏SG函数与SG定理贝亚蒂定理 (Beatty Sequence)威佐夫博弈⽣成和构造 (Generating and Construction)幻⽅构造格雷码 (Gray Code)黄⾦分割⽐Java⾼精度版常数π⽣成⼀般⽅法数值⽅法常数e⽣成Calendar(⽇历)公历瑞年判断与计数判断规则计数⽅法Zeller formula (蔡勒公式)【待测试】儒略历时期公式集合闵可夫斯基和平⾯⼏何实⽤函数平⽅函数符号函数误差修正精度-0修正符号函数等于误差修正⽐较误差修正定义域修正⼆维向量类（平⾯点类）基向量旋转公式浮点向量类整数向量类⾓度⾓度弧度换算距离Euclidean Distance(欧⽒距离)Manhattan Distance(曼哈顿距离)Chebyshev Distance(切⽐雪夫距离)⼆维线性变换(2D Linear Transformation)旋转90°旋转缩放正交投影(Orthogonal projection)镜像剪切(shear)线段 (Segment)点到直线距离点到线段距离线段到线段距离点在直线上的投影（垂⾜）过⼀点作直线的垂线直线平⾏判断判断点是否在直线上判断点是否在线段上判断点是否在射线上直线相交检测射线相交检测线段相交检测线段与线段交点直线法向平移三⾓形三⾓形⾯积四边形四边形⾯积多边形 (Polygon)数据类型判断点是否在多边形内半平⾯交圆 (Circle)数据类型圆与直线交点圆与圆交点【Note: 证明有待补充】点阵⽔平翻转竖直翻转顺时针旋转90°顺时针旋转180°逆时针旋转90°凸包Graham Scan Method单调链法分治法Akl-Toussaint heuristics method三维⼏何混合积(Triple Product)三维向量类（三维点类）罗德⾥格旋转公式三维线性变换(3D Linear Transformation)旋转缩放正交投影(Orthogonal projection)镜像剪切(shear)平⾏六⾯体平⾏六⾯体体积I/OFast cin/coutFast I/O classEOF Valid VersionBasic Input Version附录A-100以内阶乘（factorials）附录B-2的100以内次幂附录C-100以内欧拉函数值附录D-前100个素数附录E-三⾓公式基本关系和差⾓公式欧拉公式正弦定理余弦定理辅助⾓公式附录F-变换线性变换仿射变换可逆变换等⾓变换正交变换刚体变换欧式变换变换所具有的性质变换矩阵的构造变换矩阵的组合附录G-解析⼏何公式定⽐分点公式附录H-对拍、批处理与数据⽣成器Windows对拍批处理批量输⼊数据⽂件⽣成批量输出结果⽂件⽣成随机数Linuxpause对拍批量输⼊数据⽂件⽣成随机数平台通⽤C++随机数据⽣成器附录I-Linux简单操作打开⽂件夹创建⽂件夹调⽤编译器控制台输⼊⽂件结尾标识显⽰当前路径附录J-微积分差分运算前向差分逆向差分差分序列还原附录K-溢出检测加法溢出检测⽆符号数运算有符号数运算减法溢出检测乘法溢出检测逆运算检测扩位后截断检测附录L-乘法公式三数和平⽅公式平⽅和公式平⽅差公式⽴⽅和差公式附录M-杨辉三⾓