《我的所有优质博客全部开源啦我自己原创的ACM模板算法全家桶算法竞赛中的初等数论 PDF免费下载_1.docx》由会员分享，可在线阅读，更多相关《我的所有优质博客全部开源啦我自己原创的ACM模板算法全家桶算法竞赛中的初等数论 PDF免费下载_1.docx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、我的所有优质boke全部开源啦（我自己原创的ACM模板算法全家桶算法竞赛中的初等数论PDF免费下载）一直以来收到了大众的支持与鼓励非常感谢大众的支持一直捏也有很多人想要文章的PDF版本可以下载下来更好的浏览可以打印下来用作模板等等十分是这位同学所以今天我决定开源啦我的文章的PDF版本的文章全部免费送给大众然后连夜进展整理为此我创立了一个微信公众号嘿嘿嘿叫做繁凡的小岛来信首先是声明声明所有文章中的代码包括所有的模板代码固然根本上都经过了少量测试但仍可能会出现一些不可预知的bug在赛场上假如因为我的代码存在的一些bug产生的一切后续影响我概不负责_所以打印、抄写代码需慎重尽量自己理解算法含义以我的
2、代码为参考自行完成代码实现所有的资源均为繁凡整理创作而成固然免费开放电子版供个人学习使用但是未经答应不能用于任何个人或企业的商业用处违法盗版以及销售必究其法律责任。繁凡2021年度11月13日领取方式如下关注微信公众号繁凡的小岛来信请不要领完之后白嫖取关哦下个月我会给你们一个惊喜q(q)中国人不骗中国人回复繁凡的数论即可获得?算法竞赛中的初等数论?每章的PDF资源和全部的PDF资源还包含后几章没有更新到boke中的内容哦q回复繁凡的算法全家桶即可获得ACM算法全家桶的全部PDF资源包含?多项式全家桶?组合数学全家桶?线性代数全家桶?生成函数全家桶?群论全家桶?计算几何全家桶一、二、三?博弈论全
3、家桶?概率与期望全家桶?全部打包送给大众回复繁凡的ACM模板即可获得400页的ACM模板模板目录我丢在本文末尾了回复繁凡的数据构造即可获得?数据构造?C语言版清华严蔚敏考研版全书知识梳理练习习题详解的PDF版本资源注数据构造这个系列完成度实际上不是很高里面的很多内容非常的简陋是我早期的作品所以之后我会对它进展大规模的更新完善尽情期待哦?数据构造知识梳理?还没整理好明天更新繁凡的ACM模板目录目录ACM模板1一、C头文件汇总13二、动态规划161.背包162.树形DP193.数位DP204.DP的优化225.插头DP276.最长上升子序列与最长公共子序列306.1最长上升子序列LIS306.1.
4、1树状数组优化O(nlogn)306.2最长公共子序列LCS316.2.1转换成LIS优化O(nlogn)31三、字符串321.KMP322.Trie树332.1Trie树模板332.2可持久化trie树、求最大区间异或者以及353.AC自动机363.1求有多少个形式串在文本串里出现过373.2建fail树dfs求每个形式串在文本串中的出现次数383.3ac自动机fail树上dfs序建可持久化线段树404.字符串哈希434.1字符串哈希434.2二分哈希445.字符串的最小表示446.manacher算法O(n)判断回文串467.后缀数组SA467.1DA倍增算法O(nlogn)47DC3模板
5、(时间复杂度O(N),空间复杂度O(3N)488.后缀自动机SAM498.1求子串最大出现次数498.2求不同子串的种类498.3长度为k的字符串的个数498.4计算所有子串的以及0-9表示498.5给定形式串sn个匹配串str508.6求每个匹配串的循环同构可以匹配的子串总数508.7SAM转后缀树(子串排序重连后询问第k个字符)529.编辑间隔54四、数据构造541.简单数据构造551.1单链表551.2双链表551.3栈551.4循环队列561.7堆561.8一般哈希572.并查集582.1朴素并查集582.2维护size的并查集582.3维护到祖宗节点间隔的并查集592.4途径压缩以及
6、按秩合并592.5边带权60带权并查集求二分图最小环622.6扩展域632.7集合中单个元素的删除643.树状数组653.1树状数组求逆序对653.2区间修改、单点求值673.3区间修改、区间求以及673.4单点修改、区间求最值683.5实时求出剩余的数中的第k小的数树状数组二分693.6离线树状数组查询区间数的种类703.7二维树状数组713.7.1单点修改区间查询713.7.2区间修改单点查询733.7.3区间修改区间查询733.7.4矩阵取反单点查询744.线段树754.1懒惰标记754.2扫描线法(面积)784.3扫描线法周长804.4二维线段树-矩形树824.5三维线段树-空间树84
7、4.6线段树上二分查询某个点向一个方向连续值一样区间844.7离散数学应用线段树开闭区间表示844.8动态开点线段树合并优化空间874.9权值线段树区间第k小904.10线段树分治删除一些边询问是否为二分图905.平衡树915.1FQH-treap非旋平衡树915.1.1按权值分裂925.1.2按排名分裂945.2文艺平衡树985.3可持久化序列1006.可持久化线段树(主席树)1036.1查询区间第k大值1036.2带修改动态查询区间第k大值1057.单调栈与单调队列1067.1单调栈1067.2单调队列1087.3单调队列求矩阵的以及1088.ST表静态查询区间最值1108.1一维RMQ问
8、题1108.2二维RMQ问题1119.莫队1129.1根底莫队1129.2带修莫队1169.3回滚莫队1204.树上莫队123五、图论1271.最短路1271.1线段树优化的Dijkstra1281.1.1途径复原1301.2可以处理负权值的SPFA1321.2.1SPFA的SLF优化1331.2.2SPFA的LLL优化1341.2.3SPFA的DFS优化适用于负环的判断1341.3.两种分层图最短路1351.3.1分层次1351.3.2分维度1361.4Floyd算法传递闭包1371.5最小环问题1382.最长路1403.k短路1413.1两点间k短路1434.欧拉回路1444.1非递归版1
9、454.2普通递归版1454.3Hierholzers算法输出字典序最小的答案1464.4Fleury算法1464.5究极优化版1474.6混合图欧拉回路1494.7中国邮递员问题欧拉回路、状压DP1515.最小生成树1525.1kruskal算法1525.2prim算法1535.3Boruvka算法1555.4生成森林问题K颗树1575.5最小生成树的唯一性1575.6严格次小生成树1585.7LCA优化的次小生成树1585.8瓶颈生成树1615.9最小瓶颈路1615.9.1单次查询1615.9.2屡次查询1615.10Kruskal重构树1625.11最小生成树计数1645.12曼哈顿最小
10、生成树1666.最小树形图朱刘算法1686.1给定一个根的有向图的最小树形图1686.2为给定根的树形图1696.3判断无解的方法1697.负环与01分数规划1697.1判断负环1697.201分数规划1707.3判负环时TLE的优化技巧1707.4经历trick1707.5使用stack1718.树上问题1728.1树的直径1728.1.1树形DP1728.1.2两次DFS/BFS找到直径的两个端点1738.2动态修改树的边权并求每个时刻的直径线段树1758.3树的重心1769.最近公共祖先1779.1LCA的在线倍增算法1779.2LCA的离线Tarjan算法1799.3树上差分18010
11、.有向图的连通性18410.1tarjan模板18410.2最大半连通子图18610.3tarjan缩点记忆化搜索18810.4几个有向图连通性的结论19011.无向图的连通性19211.1tarjan算法求无向图的桥、边双连通分量并缩点19211.2tarjan算法求无向图的割点、点双连通分量并缩点19411.3结论变成边双连通分量所需要新建的边数19511.4动态求解当前图中的桥的数目割边缩点并查集lca优化O(mqlogn)19812.2-SAT问题20112.12-SAT模板20112.2最小字典序解20312.32-SAT二分答案20513.拓扑排序20713.1toposort模板
12、20713.2拓扑排序判断是否有环20813.3已有编号求字典序最小的拓扑序优先队列20913.4给所有点分配编号使得拓扑序的字典序最小反图、优先队列21013.5可达性统计拓扑排序bitset优化2111.1DAG中从每个点出发能到达的点的数量2111.2DAG最多删除多少条边仍可保证其连通性21113.6(2019年度南京C题)拓扑排序递推DP经典21214.二分图包含全套常用定理性质21314.1染色法判断二分图21414.2增广路的性质21514.3一些二分图的概念以及定理21514.4增广路定理21614.5二分图最大匹配21614.6二分图完美匹配21614.7匈牙利算法21614
13、.8二分图匹配模型的两个要素21714.9二分图最小点覆盖的一个要素21714.10DAG的最小途径点覆盖21714.11DAG的最小可重复途径点覆盖21714.12最小可重复途径点覆盖模板21714.13二分图的多重匹配21915.一般图最大匹配带花树22015.1一般图最大匹配22015.2一般图最大权匹配22216.KM算法二分图最大权完美匹配227O(n3)的ttBFS迭代版本22717.最小斯坦纳树(求联通k个关键点最小的代价)22918.基环树23018.1找环23118.2求基环树森林的直径23219.支配树/灭绝树23420.树的最大匹配23720.1树上DP-求树的最大匹配数
14、23821.最大团23821.1Bron-Kerbosch算法爆搜求最大团23821.2最大独立集转反图最大团23922.弦图24122.1弦图的断定24122.2弦图的最小染色问题24223.竞赛图有向完全图24323.1兰道定理243例题HDU5873FootballGames24423.2求竞赛图的任意三元环24523.3求竞赛图的哈密顿回路数量的期望24524.哈密顿问题24724.1根本概念24724.2状压DP求最短Hamilton24824.3dfs搜索求哈密尔顿回路24824.4Dirac定理下构造无向图的哈密顿回路24924.5N阶竞赛图下构造有向图的哈密顿通路25225.树
15、的计数25325.1textprufer序列25325.2textprufer序列的性质25325.3textCayley公式的推论25325.4【模板】Prufer序列253六、网络流2541.最大流2541.1Dinic2541.2ISAP2561.3Push-Relabel预流推进算法2581.4通用的预流推进算法2581.4.1HLPP算法2582.最小割2602.1集合划分模型2602.2点边转化2622.3最小割的可行边与必须边2632.4二分图的可行边以及必须边2642.5平面图最小割2642.6最小割的一些小技巧2652.6.1记录划分方案2652.6.2求割边数量2652.6
16、.3求最小边的最小割2652.6.4输出任意一种最小割的方案2652.6.5判断一条边是否满流2652.6.6判断某一条边是否可能为最小割中的一条2652.6.7判断某一条边是否为最小割中的一条2662.6.8判断某条边是否一定出如今最小割中2663.费用流2663.1最小费用最大流2663.1.1类dinic模板2663.1.2ZKW费用流2683.2最大费用最大流2703.3解决二分图带权最大匹配2703.4费用提早计算动态开点2724.上下界网络流2724.1无源汇上下界可行流2724.2有源汇有上下界可行流2744.3有源汇上下界最大流2744.4有源汇上下界最小流276七、数论278
17、1.根底数论278试除法断定质数278试除法分解质因数278朴素筛法求素数279线性筛法求素数279试除法求所有约数279约数个数以及约数之以及280欧几里得算法280求欧拉函数280筛法求欧拉函数280快速幂281扩展欧几里得算法281高斯消元281递归法求组合数282通过预处理逆元的方式求组合数282Lucas定理283分解质因数法求组合数283卡特兰数285NIM游戏285SG函数2852.质数筛法286线性筛法286二次筛法2863.分解质因数287试除法分解质因数287PollardRho因数分解287快速质因数分解阶乘2884.线性基2895.质数2901.暴力判2902.Mill
18、erRabin2903.埃氏筛2914.欧拉筛2925.Min_25筛法快速求素数以及2926.约数2931.欧几里得(gcd)2932.欧拉函数埃氏筛2933.欧拉函数欧拉筛2947.同余2941.逆元294(1).递推294(2).快速幂2943.扩展欧拉定理2954.扩展欧几里得(Exgcd)同余方程2955.中国剩余定理(CRT)2966.扩展中国剩余定理(EXCRT)2977.拔山盖世/大步小步/BSGS(BabyStepsGiantSteps)2978.扩展BSGS(EXBSGS)2989.二次剩余30010.N次剩余3018.类欧几里得算法3039.各类反演及数论筛法3051.莫
19、比乌斯函数(Mobius)3052.杜教筛306(1).map记忆化306(2).数组记忆化3073.最值反演(Min-Max容斥)308八、计算几何3081.计算几何考前须知3081.1计算误差3091.2解决方案:误差判别法3091.3解决方案化浮为整3091.4注意负零3091.5注意反三角函数的值域3091.6计算几何常用开始模板3092.考前须知3103.几何公式3101.三角形3112.四边形3113.正n边形3114.圆3115.棱柱3116.棱锥3127.棱台3128.圆柱3129.圆锥31210.圆台31211.球31212.球台31213.球扇形312二维几何根底3131.
20、根本运算3131.1判断正负函数(sgn)3141.2点积数量积、内积(Dot)3141.3向量积叉积(Cross)3141.4取模求长度(Length)3151.5计算两向量夹角(Angle)3151.6计算两向量构成的平行四边形有向面积(Area2)3151.7计算向量逆时针旋转后的向量(Rotate)3151.8计算向量逆时针旋转九十度的单位法线(Normal)3151.9判断折线向量bc是不是向向量ab的逆时针方向左边转向(ToLeftTest)3151.10点绕着p点逆时针旋转angle(rotate)3151.11判断点以及直线关系(relation)3161.12复数表示3162
21、.点与线3162.1直线的实现(Line)3172.2判断点在直线上3172.3计算两直线交点(Get_line_intersection)3172.4计算点到直线的间隔(Distance_point_to_line)3172.5计算点到线段的间隔(Distance_point_to_segment)3172.6求点在直线上的投影点(Get_line_projection)3172.7判断点是否在线段上(OnSegment)3182.8判断两线段是否相交不算在端点处相交(segment_proper_intersection)3182.9判断两线段是否相交包含端点处相交(Segment_pro
22、per_intersection)3182.10判断点是否在一条线段上(不含端点)(on_segment)3192.11两向量的关系(parallel)3192.12两直线关系(linecrossline)3193.多边形3193.0.三角形3193.0.1三角形四心3203.0.2关键点与A,B,C三顶点间隔之以及3203.0.2.1费马点3203.0.3向量求三角形垂心(getcircle)3203.1.0正多边形的一些性质以及概念3213.1求多边形面积(convex_polygon_area)3213.2判断点在多边形内(is_point_in_polygon)3223.3判断点在凸多
23、边形内3223.4求多边形重心(barycenter)3223.5断定凸多边形(is_convex)3233.6判点在凸多边形内或者多边形边上(inside_convex)3233.7判点在任意多边形内(inside_polygon)3233.8判线段在任意多边形内(inside_polygon)3233.9多边形切割(常用于半平面交)3254.圆3264.1圆与直线交点(getLineCircleIntersection)3264.2求两圆交点(get_circle_circle_intersection)3274.3点到圆的切线(get_tangents)3274.4两圆的公切线(get_
24、tangents)3284.5两圆相交面积(AreaOfOverlap)3284.6模板合集3294.7判直线以及圆相交(intersect_line_circle)3294.8判线段以及圆相交(intersect_seg_circle)3294.9判圆以及圆相交(intersect_circle_circle)3304.10计算圆上到点p最近点(dot_to_circle)3304.11计算直线/线段与圆的交点intersection_line_circle3304.12计算圆与圆的交点intersection_circle_circle3304.13求圆外一点对圆的两个切点(Tangent
25、Point_PC)3314.14求三角形的外接圆(get_circumcircle)3314.15求三角形的内接圆(get_incircle)3314.16二维几何110_2合一3324.17经纬度转换为空间坐标3344.18球面间隔3344.19三点确定一圆3344.20两个圆的关系(relationcircle)3355.网格3365.1多边形上的网格点个数3365.2多边形内的网格点个数3366.一些函数/定理/应用3366.1欧拉定理3366.2Pick定理根据点在多边形内以及边界的个数求面积3376.3判断四点共面混合积3387.平面扫描3398.凸包3408.1Andrew算法34
26、08.2直线两点式转为一般式使用公式O(1)计算点到直线间隔3418.3判断点是否在凸包内3429.旋转卡壳3429.1求凸包的直径3429.2求两个凸多边形(凸包)间最小间隔34410.半平面交34510.1有向直线34610.2O(nlogn)的半平面交34610.3二分半平面交34711.闵可夫斯基以及34812.平面区域34813.平面最近点对35014.三维根底操作3531.1三维点积(Dot3)3541.2三维叉积(Cross3)3541.3矢量差Subt3551.4.1返回abacad的混合积(Volume6)3551.4.2四面体体积(Volume6)3561.5求四面体的重心
27、(Centroid)3561.6凸多面体的重心3561.7二面角35715.三维点线面3572.1取平面法向量(NormalVector)3572.2求两点间隔(TwoPointDistance)3572.3点p到平面的间隔(DistanceToPlane)3582.4点p在平面上的投影(GetPlaneProjection)3582.5直线与平面的交点(LinePlaneIntersection)3582.6空间直线间隔(LineToLine)3582.7点到直线的间隔(DistanceToLine)3582.8点到线段的间隔(DistanceToSeg)3582.9求异面直线与的公垂线对应
28、的s(LineDistance3D)3592.10p1以及p2是否在线段a-b的同侧(SameSide)3592.11判断点P是否在三角形中(PointInTri)3592.12三角形P0、P1、P2是否以及线段AB相交(TriSegIntersection)3592.13空间两三角形是否相交(TriTriIntersection)3602.14空间两直线上最近点对返回最近间隔(SegSegDistance)3602.15判断P是否在三角形A,B,C中并且到三条边的间隔都至少为mindist(InsideWithMinDistance)3602.16判断P是否在凸四边形中并且到四条边的间隔都至
29、少为mindist(InsideWithMinDistance)36116.三维凸包3613.1加干扰防止多点共面(add_noise)3613.2凸包的定义(Face)3623.3增量法求三维凸包(CH3D)3623.4凸多面体(ConvexPolyhedron)3633.5给三维凸包求出重心到各面的最小间隔。36417.最小圆覆盖36918.三角剖分(求圆与三角形的公共面积)37019.K次圆覆盖372九、其他Other3751.常用函数3751.1全排列next_permutation3751.2读写优化3751.3返回容器内最大最小值3761.4复制函数3761.5容器删除函数3771
30、.6容器填充函数3771.7查找函数3771.8字符串转换整数/数字转字符串3781.9取局部字符串函数3782.高精度计算3793.离散化3804.根底算法3814.1快速排序3814.2归并排序3824.3整数二分3824.4浮点数二分3824.5高精度加法3834.6高精度减法3834.7高精度乘低精度3834.8高精度除以低精度3844.9一维前缀以及3844.10二维前缀以及3844.10.1二维前缀以及求矩阵以及3844.11一维差分3854.12二维差分3854.12.1区间修改使得数列全部相等的最小次数3854.13双指针算法3864.14区间合并3864.15龟速乘3865.表达式求值3875.1表达式求值前中后3875.2递归法求中缀表达式的值O(n2)3875.3后缀表达式转中缀表达式同时求值O(n)3885.4中缀表达式转后缀表达式同时对后缀表达式求值3896.递归3896.1奇怪的汉诺塔n盘m柱3896.2分形递归390lowbithash找出二进制下所有1的位数3917.二分以及三分3917.1三分法求单峰函数的极值3917.2二分求序列最大平均值3928.矩阵快速幂3939.set以及multiset39410.bitset的用法39511.进制转换n进制转m进制39612.java高精度396