cjdjr / algorithmic_template

🍭LzyRapx 's algorithmic library for competitive-programming. Some templates for ACMer, OIer, Algorithmser etc.

Algorithmic_Library

LzyRapx 's code Library for competitive-programming.

Black_magic

• 手写bitset
• fastIO
• pb_ds
• rope
• 扩栈
• O(1)快速乘

Class

• BigInt
• Frac
• 对拍

DataStructure

• CDQ分治
• Dancing Links X (DLX)
• HASH
• KMP
• LCA
• LCT
• Splay Tree
• merge_sort

Geometry

• 基本类型 - 点, 线
• 多边形
• 半平面交
• 圆
• 三维几何
• 球面几何
• 平面最近点对
• 曼哈顿距离生成树
• 最大空凸包
• 平面图求域

Graph-theory

• Connectivity
  • BCC
  • BCC_edge
  • BCC_vertex
  • Kosaraju
  • Tarjan_SCC
• Flows and cuts
  • Dinic
  • Edmonds–Karp
  • Ford-Fulkerson
  • MinCostMaxFlow
  • edge-disjoint-path
  • maximum_flow_goldberg_tarjan
• Matching
  • Kuhn-Munkras
  • Hungarian method (匈牙利算法)
• Shortest-path
  • Bellman-Ford
  • Dijkstra
  • Floyd–Warshall
  • K短路
  • SPFA
• Spanning-tree
  • Kruskal (MST和次小生成树)
  • prim
  • 曼哈顿距离MST

Mathematics

• BSGS
• Berlekamp-Massey
• Berlekamp-Massey (杜教版)
• CRT（模数不互质）
• CRT（模数互质）
• Cantor
• Check_primitive_root
• Dirichlet卷积
• EX_BSGS
• Euler_Function
• Extends_GCD
• FFT+CDQ
• FFT大整数乘法
• MTT
• Fib数模n的循环节
• Guass
• [1,n]与a互素个数
• bernoulli_number
• factorial
• gauss_elimination
• 任意模数FFT+多项式取逆
• 康拓展开和逆康拓展开
• 快速幂
• 杜教筛
• 线性筛prime+phi+mu

String

• AhoCorasick (AC自动机)
• EX_KMP
• KMP
• LIS
• Manacher
• SA
• String Hash
• suffix array
• 回文树
• 动态Trie
• 静态Trie

Others