forked from tabris233/template
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtabris-template.toc
114 lines (114 loc) · 8.58 KB
/
tabris-template.toc
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
\contentsline {part}{I\hspace {1em}Graph Theory}{1}{part.1}
\contentsline {section}{\numberline {1}Basement}{1}{section.1}
\contentsline {subsection}{\numberline {1.1}Representation}{1}{subsection.1.1}
\contentsline {section}{\numberline {2}Shortest Path}{1}{section.2}
\contentsline {subsection}{\numberline {2.1}SPFA}{1}{subsection.2.1}
\contentsline {subsection}{\numberline {2.2}Dijkstra}{2}{subsection.2.2}
\contentsline {section}{\numberline {3}Minimum Spanning Tree}{2}{section.3}
\contentsline {subsection}{\numberline {3.1}Kruskal}{2}{subsection.3.1}
\contentsline {subsection}{\numberline {3.2}Prim}{3}{subsection.3.2}
\contentsline {section}{\numberline {4}Directed Graph}{5}{section.4}
\contentsline {subsection}{\numberline {4.1}Topological Sorting}{5}{subsection.4.1}
\contentsline {section}{\numberline {5}Bipartite Graph}{6}{section.5}
\contentsline {subsection}{\numberline {5.1}Hungary}{6}{subsection.5.1}
\contentsline {subsection}{\numberline {5.2}Two Set}{7}{subsection.5.2}
\contentsline {section}{\numberline {6}Strongly Connected}{9}{section.6}
\contentsline {subsection}{\numberline {6.1}tarjon}{9}{subsection.6.1}
\contentsline {section}{\numberline {7}Tree}{10}{section.7}
\contentsline {subsection}{\numberline {7.1}centre of gravity of tree}{10}{subsection.7.1}
\contentsline {subsection}{\numberline {7.2}Least Common Ancestors}{11}{subsection.7.2}
\contentsline {section}{\numberline {8}Network Flows}{12}{section.8}
\contentsline {subsection}{\numberline {8.1}Dinic}{12}{subsection.8.1}
\contentsline {subsection}{\numberline {8.2}ISAP}{12}{subsection.8.2}
\contentsline {part}{II\hspace {1em}String}{15}{part.2}
\contentsline {section}{\numberline {9}String Match}{15}{section.9}
\contentsline {subsection}{\numberline {9.1}KMP}{15}{subsection.9.1}
\contentsline {subsection}{\numberline {9.2}Trie}{15}{subsection.9.2}
\contentsline {subsection}{\numberline {9.3}Aho Corasick Auto Mation}{18}{subsection.9.3}
\contentsline {subsection}{\numberline {9.4}Suffix Arrays}{19}{subsection.9.4}
\contentsline {subsection}{\numberline {9.5}Suffix Automaton}{21}{subsection.9.5}
\contentsline {section}{\numberline {10}Manachar}{22}{section.10}
\contentsline {part}{III\hspace {1em}Data structure}{23}{part.3}
\contentsline {section}{\numberline {11}UFS}{23}{section.11}
\contentsline {section}{\numberline {12}BIT}{25}{section.12}
\contentsline {section}{\numberline {13}Segment tree}{26}{section.13}
\contentsline {section}{\numberline {14}Chair tree}{35}{section.14}
\contentsline {section}{\numberline {15}Splay}{38}{section.15}
\contentsline {section}{\numberline {16}Link Cut Tree}{45}{section.16}
\contentsline {section}{\numberline {17}KD-tree}{49}{section.17}
\contentsline {section}{\numberline {18}tranform : tree -> arrary}{50}{section.18}
\contentsline {subsection}{\numberline {18.1}dfs order}{50}{subsection.18.1}
\contentsline {subsection}{\numberline {18.2}Heavy light Decomposition}{51}{subsection.18.2}
\contentsline {section}{\numberline {19}SparseTable}{52}{section.19}
\contentsline {section}{\numberline {20}Leftist Tree}{53}{section.20}
\contentsline {part}{IV\hspace {1em}Math}{54}{part.4}
\contentsline {section}{\numberline {21}Number Theory}{54}{section.21}
\contentsline {subsection}{\numberline {21.1}Basement}{54}{subsection.21.1}
\contentsline {subsubsection}{\numberline {21.1.1}inverse}{54}{subsubsection.21.1.1}
\contentsline {subsubsection}{\numberline {21.1.2}Guass}{54}{subsubsection.21.1.2}
\contentsline {subsubsection}{\numberline {21.1.3}linear basis}{57}{subsubsection.21.1.3}
\contentsline {subsection}{\numberline {21.2}Congruence problem}{58}{subsection.21.2}
\contentsline {subsubsection}{\numberline {21.2.1}gcd}{58}{subsubsection.21.2.1}
\contentsline {subsubsection}{\numberline {21.2.2}China remainder theory}{58}{subsubsection.21.2.2}
\contentsline {subsubsection}{\numberline {21.2.3}Function Of Congruence}{59}{subsubsection.21.2.3}
\contentsline {subsection}{\numberline {21.3}Prime}{60}{subsection.21.3}
\contentsline {subsubsection}{\numberline {21.3.1}Sieve}{60}{subsubsection.21.3.1}
\contentsline {subsubsection}{\numberline {21.3.2}Fundamental Theorem of Arithmetic}{61}{subsubsection.21.3.2}
\contentsline {subsubsection}{\numberline {21.3.3}Miller Rabbin}{61}{subsubsection.21.3.3}
\contentsline {subsubsection}{\numberline {21.3.4}Pollard Rho}{62}{subsubsection.21.3.4}
\contentsline {subsubsection}{\numberline {21.3.5}count primes}{63}{subsubsection.21.3.5}
\contentsline {subsection}{\numberline {21.4}Multiplicative Function}{65}{subsection.21.4}
\contentsline {subsubsection}{\numberline {21.4.1}Euler Function}{65}{subsubsection.21.4.1}
\contentsline {subsection}{\numberline {21.5}Fast Calculation}{67}{subsection.21.5}
\contentsline {subsubsection}{\numberline {21.5.1}Fast Exponentiation Mod}{67}{subsubsection.21.5.1}
\contentsline {subsubsection}{\numberline {21.5.2}Fast Multi}{67}{subsubsection.21.5.2}
\contentsline {subsubsection}{\numberline {21.5.3}Fast Sqrt}{67}{subsubsection.21.5.3}
\contentsline {subsubsection}{\numberline {21.5.4}Matrix}{67}{subsubsection.21.5.4}
\contentsline {subsubsection}{\numberline {21.5.5}Fast Fourier Transform}{68}{subsubsection.21.5.5}
\contentsline {subsubsection}{\numberline {21.5.6}Fast Number Theoretic Transform}{69}{subsubsection.21.5.6}
\contentsline {subsubsection}{\numberline {21.5.7}Fast Walsh Transform}{70}{subsubsection.21.5.7}
\contentsline {subsection}{\numberline {21.6}Primitive Root}{70}{subsection.21.6}
\contentsline {section}{\numberline {22}Combinatorial mathematics}{72}{section.22}
\contentsline {subsection}{\numberline {22.1}combinatorial number}{72}{subsection.22.1}
\contentsline {subsubsection}{\numberline {22.1.1}M个盘子取N个球}{72}{subsubsection.22.1.1}
\contentsline {subsubsection}{\numberline {22.1.2}Pascal's Triangle}{72}{subsubsection.22.1.2}
\contentsline {subsubsection}{\numberline {22.1.3}factorial/inverse}{73}{subsubsection.22.1.3}
\contentsline {subsubsection}{\numberline {22.1.4}Lucas}{73}{subsubsection.22.1.4}
\contentsline {subsection}{\numberline {22.2}Catalan number}{73}{subsection.22.2}
\contentsline {subsection}{\numberline {22.3}Stirling number[one]}{73}{subsection.22.3}
\contentsline {subsection}{\numberline {22.4}Stirling number[two]}{74}{subsection.22.4}
\contentsline {subsection}{\numberline {22.5}Bell number}{74}{subsection.22.5}
\contentsline {subsection}{\numberline {22.6}Principle of inclusion-exclusion}{74}{subsection.22.6}
\contentsline {subsection}{\numberline {22.7}Möbius inversion formula}{75}{subsection.22.7}
\contentsline {section}{\numberline {23}Game Theory}{77}{section.23}
\contentsline {subsection}{\numberline {23.1}Wythoff Game}{77}{subsection.23.1}
\contentsline {subsubsection}{\numberline {23.1.1}Sprague Grundy}{77}{subsubsection.23.1.1}
\contentsline {part}{V\hspace {1em}Computational Geometry}{78}{part.5}
\contentsline {section}{\numberline {24}向量旋转}{78}{section.24}
\contentsline {section}{\numberline {25}Various Code}{78}{section.25}
\contentsline {subsection}{\numberline {25.1}2-D}{78}{subsection.25.1}
\contentsline {subsection}{\numberline {25.2}3-D}{86}{subsection.25.2}
\contentsline {part}{VI\hspace {1em}STL}{88}{part.6}
\contentsline {section}{\numberline {26}Set}{88}{section.26}
\contentsline {section}{\numberline {27}Multiset}{88}{section.27}
\contentsline {section}{\numberline {28}bitset}{88}{section.28}
\contentsline {section}{\numberline {29}Map}{89}{section.29}
\contentsline {section}{\numberline {30}HashMap}{90}{section.30}
\contentsline {section}{\numberline {31}Queue}{90}{section.31}
\contentsline {part}{VII\hspace {1em}Other}{92}{part.7}
\contentsline {section}{\numberline {32}Divide}{92}{section.32}
\contentsline {subsection}{\numberline {32.1}Normal Divide}{92}{subsection.32.1}
\contentsline {subsection}{\numberline {32.2}Tree Divide}{93}{subsection.32.2}
\contentsline {subsubsection}{\numberline {32.2.1}Point Divide}{93}{subsubsection.32.2.1}
\contentsline {subsubsection}{\numberline {32.2.2}Edge Divide}{95}{subsubsection.32.2.2}
\contentsline {subsection}{\numberline {32.3}CDQ Divide}{99}{subsection.32.3}
\contentsline {section}{\numberline {33}手动开栈}{100}{section.33}
\contentsline {section}{\numberline {34}fastIO}{100}{section.34}
\contentsline {section}{\numberline {35}Hash}{101}{section.35}
\contentsline {subsection}{\numberline {35.1}Cantor expension}{101}{subsection.35.1}
\contentsline {subsection}{\numberline {35.2}String Hash}{101}{subsection.35.2}
\contentsline {section}{\numberline {36}BigNumber}{102}{section.36}
\contentsline {subsection}{\numberline {36.1}C++ bignumber}{102}{subsection.36.1}
\contentsline {subsection}{\numberline {36.2}Java Bignumber}{102}{subsection.36.2}
\contentsline {section}{\numberline {37}polynomial gcd}{103}{section.37}
\contentsfinish