forked from wcysai/code_library
-
Notifications
You must be signed in to change notification settings - Fork 0
/
scl.yaml
292 lines (292 loc) · 10.9 KB
/
scl.yaml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
- name: General
dir: general/
files:
- title: Code library checksum
fname: checksum.py
- title: Makefile
fname: Makefile.txt
- title: .vimrc
fname: vimrc.txt
- title: Stack
fname: stack.cpp
- title: Template
fname: template.cpp
- name: Miscellaneous Algorithms
dir: misc/
files:
- title: Convex Hull Trick
fname: ConvexHullTrick.cpp
- title: Dynamic Convex Hull Trick
fname: DynamicConvexHullTrick.cpp
- title: Isotonic Regression
fname: IsotonicRegression.cpp
desc: Given a DAG $G=(V,E)$ on $\vert V\vert=n$ vertices and initial values $a_1,a_2,\dots,a_n$ on vertices, find $b_1,b_2,\dots,b_n$ satisfying $b_u\geq b_v$ iff $(u,v)\in E$ and minimize $\sum\limits_{i=1}^{n}\vert b_i-a_i\vert$
- title: Matroid Intersection
fname: MatroidIntersection.cpp
desc: Find the maximum cardinality common independent set of two matroids. Matroids are given by independence oracle.
usage:
MatroidOracle: The independence oracle maintaining an independent set. \textbf{Note} that the default constructor must properly initialize inner state to an empty set.
insert(x): Insert element labeled x to the independent set.
test(x): Test whether the set is still independent if x is inserted.
MatroidIntersection<MT1, MT2>(n): Construct the matroid intersection solver with n elements labeled from 0 and matroid oracles \lstinline|MT1| and \lstinline|MT2|.
run(): Run the algorithm and return the matroid intersection.
- title: Weighted Matroid Intersection
fname: WeightedMatroidIntersection.cpp
desc: Find the maximum weighted common independent set of two matroids. Matroids are given by independence oracle.
- title: Multiple Knapsack
fname: MultipleBackpack.cpp
desc: Solve the knapsack problem with multiple items of each kind in $O(nW)$, optimized using monotone deque.
- title: Nim Multiplication
fname: NimMultiplication.cpp
desc: Multiplication of nimbers
- title: Simplex Algorithm
fname: Simplex.cpp
desc: Simplex algorithm for solving linear programs. Minimize $cx$ subject to $Ax\leq b$. Input format given in the code.
- title: SlopeTrick
fname: SlopeTrick.cpp
- title: Gosper's Hack
fname: Subset.cpp
desc: Find all subsets of $S$ in $O(2^{\vert S\vert})$/ all subsets of size $k$ of $S$ in $O(\binom{\vert S\vert}{k})$.
- title: Surreal Number
fname: SurrealNumber.cpp
desc: Calculation of surreal number in partizan games(with numbers only, e.g., $\star$ is not allowed).
- title: Zeller's Formula
fname: whatday.cpp
desc: Determine the day of the week given the date.
- name: String
dir: string/
files:
- title: Knuth-Morris-Pratt algorithm
fname: KMP.cpp
- title: Manacher algorithm
fname: manacher.cpp
- title: Aho-corasick automaton
fname: ACAM.cpp
- title: Trie
fname: Trie.cpp
- title: Suffix array
fname: SA.cpp
desc: Suffix array construction in $O(n\log{n})$ time
- title: SAIS
fname: SAIS.cpp
desc: Linear-time algorithm for suffix array construction
- title: Suffix automaton
fname: SAM.cpp
- name: Math
dir: math/
files:
- title: Modular Arithmetic
fname: Mod.cpp
desc: Some basic operations
- title: Berlekamp-Massey algorithm
fname: Berlekamp-Massey.cpp
- title: BigIntegers
fname: BigNum.cpp
- title: Chinese Remainder Theorem
fname: CRT.cpp
- title: Matrix Determinant
fname: Determinant.cpp
- title: DIVCNT1
fname: DIVCNT1.cpp
desc: Let $d_1(n)$ be the number of divisors of $n$. Calculate $\sum\limits_{i=1}^{n}d_1(n)$ in $O(n^{1/3}\log{n})$ time.
- title: (Quasi-)Euclidean algorithm
fname: Euclid.cpp
desc: $f(n)=\sum\limits_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$\\ $g(n)=\sum\limits_{i=0}^{n}i\cdot \lfloor\frac{ai+b}{c}\rfloor$\\ $h(n)=\sum\limits_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2$.
- title: Linear sieve
fname: EulerSieve.cpp
- title: Extended Lucas Theorem
fname: ExtLucas.cpp
desc: Calculate $\binom{n}{k}\mod m$ for $m\leq 10^6$
- title: Farey Series
fname: Farey.cpp
- title: Fast modular arithmetics
fname: FastMultiplication.cpp
- title: Fast Fourier Transform(FFT)
fname: FFT.cpp
- title: Fast Walsh-Hadamard Transform(FWT)
fname: FWT.cpp
- title: Number Theoretic Transform(NTT)
fname: NTT.cpp
- title: Gaussian Elimination
fname: GaussJordan.cpp
- title: Lagrange Interpolation
fname: Interpolation.cpp
- title: Linear Basis
fname: LinearBasis.cpp
- title: System of equations with linear congruence
fname: LinearCongruence.cpp
- title: Matrix Operations
fname: Matrix.cpp
- title: Pollard-Rho factorization with Miller-Rabin Primality test
fname: PollardRho.cpp
- title: Pell's equation
fname: Pell.cpp
- title: Pohlig-Hellman algorithm
fname: PohligHellman.cpp
- title: Matrix operations
fname: Matrix.cpp
- title: Points In A Circle
fname: PIAC.cpp
desc: Calculate the number of integer points inside a circle of radius $r$ centered at the origin.
- title: Polynomial Operations
fname: PolyOp.cpp
- title: Fast Lagrange Interpolation
fname: PolySum.cpp
- title: Power Tower
fname: PowerTower.cpp
desc: Given $a_1,\dots,a_n$, calculate $\text{pow}(a[l],\text{pow}(a[l+1],\text{pow}(\dots,a[r])))$.
- title: Counting the number(polynomial) of primes
fname: PrimeCount.cpp
desc: Let $f(x)$ be any polynomial, calculate $\sum\limits_{p\leq n\atop{p\text{ prime}}}f(p)$ in $O(\frac{\sqrt{n}}{\log{n}}\cdot \text{deg}(f))$ time, assuming the point evaluation of $f$ can be done in $O(1)$ and prefix sum can be calculated in $O(\text{deg}(f))$.
- title: Primitive Root
fname: PrimitiveRoot.cpp
- title: Schreier-Sims algorithm
fname: SchreierSims.cpp
desc: Given some permutations $P=\{p_1,p_2,\dots,p_m\}$, calculate the number of elements in the group generated by $P$.
- title: Segment Sieve
fname: SegmentSieve.cpp
- title: Simpson's algorithm
fname: Simpson.cpp
- title: Stirling number of the first kind
fname: StirlingI.cpp
- title: Stirling number of the second kind(multiple)
fname: StirlingIIM.cpp
- title: Stirling number of the first kind(single)
fname: StirlingIIS.cpp
- title: Subset convolution
fname: SubsetConvolution.cpp
desc: Given $f,g:2^{n}\rightarrow \{0,1\}$, calculate $f\circ g(s)=\sum\limits_{s'\subseteq s}f(s')g(s\setminus s')$ in $O(2^n\cdot n^2)$.
- title: Prefix Sum of Phi
fname: SumPhi.cpp
- title: Prefix Sum of Mu
fname: SumMu.cpp
- title: Tonelli-Shanks algorithm
fname: TonelliShanks.cpp
desc: Given $x,p$, determine if $x$ is a quadratic residue modulo $p$, if yes, return $0<y<p$ such that $y^2\equiv x\pmod p$.
- name: Graph Theory
dir: graph/
files:
- title: Dijkstra's algorithm(priority queue)
fname: DijkstraI.cpp
- title: Dijkstra's algorithm(brute force)
fname: DijkstraII.cpp
- title: Floyd-Warshall algorithm
fname: FloydWarshall.cpp
- title: SPFA
fname: SPFA.cpp
- title: Prim's algorithm(priority queue)
fname: PrimI.cpp
- title: Prim's algorithm(brute force)
fname: PrimII.cpp
- title: Kruskal's algorithm
fname: Kruskal.cpp
- title: Maximum Matching for bipartite graphs
fname: BipartiteMatching.cpp
- title: Maximum Matching for general graphs
fname: CommonMatching.cpp
- title: Hopcroft-Karp algorithm(faster bipartite matching)
fname: HopcroftKarp.cpp
- title: Kuhn-Munkres algorithm(minimum weight bipartite matching)
fname: KuhnMunkres.cpp
- title: Dinic's algorithm
fname: Dinic.cpp
- title: Minimum-cost flow(nonnegative weights)
fname: MinCostFlow.cpp
- title: Minimum-cost flow(supports negative weights)
fname: MinCostFlow(SPFA).cpp
- title: Gomory-Hu Tree
fname: GomoryHuTree.cpp
- title: Edge coloring for bipartite graphs
fname: BipartiteEdgeColoring.cpp
- title: Block Cut Tree
fname: BlockCutTree.cpp
- title: Bridge Tree
fname: BridgeTree.cpp
- title: Chordal Graph
fname: ChordalGraph.cpp
- title: Dominator Tree
fname: DominatorTree.cpp
- title: Dynamic Bridge
fname: DynamicBridge.cpp
- title: Dynamic Connectivity
fname: DynamicConnectivity.cpp
- title: Ear Decomposition
fname: EarDecomposition.cpp
- title: Kosaraju's algorithm
fname: Kosaraju.cpp
- title: Lowest Common Ancestor(with binary lifting)
fname: LCA.cpp
- title: Lowest Common Ancestor(with range minimum query)
fname: LCArmq.cpp
- title: Minimum Arborescence
fname: MinimumArborescence.cpp
- title: Minimum Diameter Spanning Tree
fname: MinimumDiameterSpanningTree.cpp
- title: Tarjan's algorithm
fname: Tarjan.cpp
- title: Number of cycles of length $3$
fname: TriangleCount.cpp
- title: Number of cycles of length $4$
fname: SquareCount.cpp
- title: Topological Sort
fname: TopologicalSort.cpp
- title: Chain Intersection on Tree
fname: TreeChainIntersection.cpp
- title: Centroid Decomposition
fname: CentroidDecomposition.cpp
- title: Heavy-Light Decomposition
fname: HLD.cpp
- title: Virtual Tree
fname: VirtualTree.cpp
- name: Data Structures
dir: ds/
files:
- title: Fenwick tree
fname: BIT.cpp
- title: Cartesian tree
fname: DescartesTree.cpp
- title: Disjoint Set Union
fname: DSU.cpp
- title: Li Chao Segment Tree
fname: LichaoSegmentTree.cpp
- title: Link-Cut Tree
fname: LCT.cpp
- title: Long Chain Decomposition
fname: LSD.cpp
- title: Monotone Deque
fname: MonotoneDeque.cpp
- title: Monotone Stack
fname: MonotoneStack.cpp
- title: Persistent Disjoint Set Union
fname: PersistentDSU.cpp
- title: Persistent Segment Tree
fname: PersistentSegmentTree.cpp
- title: Persistent Segment Trie
fname: PersistentTrie.cpp
- title: Mo's algorithm
fname: Mo.cpp
- title: Mo's algorithm with queries
fname: QMo.cpp
- title: Mo's algorithm on tree
fname: TreeMo.cpp
- title: Mo's algorithm on tree with queries
fname: QTreeMo.cpp
- title: Segment Tree Beats
fname: SegmentTreeBeats.cpp
- title: Segment Tree Merge
fname: SegmentTreeMerge.cpp
- title: Sparse Table
fname: SparseTable.cpp
- title: Treap
fname: Treap.cpp
- title: DSU on tree
fname: TreeDSU.cpp
- title: Young's Tableaux
fname: Young.cpp
- name: Geometrics
dir: geo/
files:
- title: 2D geometric template
fname: Basics.cpp
- title: 3D geometric template
fname: Stereometry.cpp