あるまかんライブラリ

Library Files

Algorithm

• doubling-pow() (繰り返し二乗法) (Algorithm/doubling-pow.hpp)

Data-Structure/Disjoint-Set

• Union-Find (素集合データ構造) (Data-Structure/Disjoint-Set/union-find.hpp)

Data-Structure/Range-Accumulate

• Fenwic-Tree (Binary-Indexed-Tree) (Data-Structure/Range-Accumulate/FenwicTree.hpp)
• CumulativeSum (累積和) (Data-Structure/Range-Accumulate/cumulative-sum.hpp)
• FoldLR (Data-Structure/Range-Accumulate/foldLR.hpp)

Graph/Minimum-Spanning-Tree

• kruskal() (クラスカル法) (Graph/Minimum-Spanning-Tree/kruskal.hpp)

Graph/Shortest-Path

• bfs() (幅優先探索による単一始点最短経路, 次元拡張に対応) (Graph/Shortest-Path/bfs.hpp)
• dijkstra() (ダイクストラ, $O((V + E)\log V)$) (Graph/Shortest-Path/dijkstra.hpp)

Graph

• graph-template (Edge, Graph, MatrixGraph) (Graph/graph-template.hpp)

Math/Combinatorics

• binomial() (二項係数 $O(K)$) (Math/Combinatorics/binomial-O(K).cpp)
• binomialTable() (二項係数テーブル $O(N^2)$) (Math/Combinatorics/binomial-table-O(NN).cpp)
• binomialTable_constN() (二項係数テーブル $O(K)$) (Math/Combinatorics/binomial-table-const-N.cpp)
• factorials (階乗, 階乗の逆元, nCr, nPr) (Math/Combinatorics/factorials.hpp)

Math/Modulo

• MersennePrimeNumberModInt (法がメルセンヌ素数のModInt特殊化) (Math/Modulo/mersenne-prime-number-mod-int.hpp)
• Mod-Int (コンパイル時mod型と実行時mod型) (Math/Modulo/mod-int.hpp)

Math/Number-Theory

• divisorCountTable (約数の個数のテーブル, $O(N \log N)$) (Math/Number-Theory/divisor-count-table.hpp)
• enumerateDivisors() (約数列挙) (Math/Number-Theory/enumerate-divisors.hpp)
• Eratosthenes-Sieve (エラトステネスの篩) (Math/Number-Theory/eratosthenes-sieve.hpp)
• extgcd() (拡張ユークリッドの互除法) (Math/Number-Theory/extgcd.hpp)
• isPrime() (素数判定 $O(\sqrt n)$) (Math/Number-Theory/is-prime.hpp)
• osa_k() (前計算 $O(N \log \log N)$, 素因数分解 $O(\log N)$) (Math/Number-Theory/osa_k.hpp)
• primeFactorize() (素因数分解 $O(\sqrt n)$) (Math/Number-Theory/prime-factorize.hpp)
• totient() (オイラーのトーシェント関数) (Math/Number-Theory/totient-func.hpp)

String

• rabinKarp() (ラビンカープ法, RollingHashを用いた文字列検索 $O(|s|)$) (String/rabin-karp.hpp)
• Rolling-Hash (ローリングハッシュ, mod値 $2^{61} - 1$ 固定) (String/rolling-hash.hpp)

Util/Debug

• Debug (Util/Debug/debug.hpp)
• errln() (println()のstderr版, デバッグ時のみ有効) (Util/Debug/errln.hpp)
• graph-debug (グラフのデバッグ出力) (Util/Debug/graph-debug.hpp)

Util/IO

• std::istreamによるコンテナの入力 (Util/IO/container-input.hpp)
• std::ostreamによるコンテナの出力 (Util/IO/container-output.hpp)
• join() (要素を区切り文字で結合して出力) (Util/IO/join-into-ostream.hpp)
• println() (可変個の値を空白区切りで出力して改行する) (Util/IO/println.hpp)
• readDirectedGraph() (有向グラフの入力) (Util/IO/read-directed-graph.hpp)
• readUndirectedGraph() (無向グラフの入力) (Util/IO/read-undirected-graph.hpp)
• read() (n個入力してContainerに格納して返す) (Util/IO/read.hpp)
• 複数変数宣言をして同時に入力もするやつ (Util/IO/var-declaration-with-input.hpp)

Util

• all()マクロ (Util/all-macro.hpp)
• at() () (Util/at.hpp)
• chmin(), chmax() (Util/chminmax.hpp)
• constexprRandint() (コンパイル時乱数) (Util/constexpr-randint.hpp)
• cstringHash() ヌル文字終端された文字列から32bitハッシュ値を生成する(constexpr) (Util/cstring-hash.hpp)
• fillContainer() (コンテナのfill) (Util/fillContainer.hpp)
• FixPoint (ラムダ式の再帰) (Util/fix-point.hpp)
• IndexingWrapper (Util/indexing-wrapper.hpp)
• int-alias (整数型のエイリアス) (Util/int-alias.hpp)
• int-infinity (整数のデカイ値) (Util/int-infinity.hpp)
• within() (半開区間内に含まれているかの判定) (Util/is-within-range.hpp)
• makeFourNeighborEnumerator() (グリッドの四近傍(上下左右)の列挙) (Util/make-four-neighbor-enumerator.hpp)
• makeVec() (多次元std::vectorの生成) (Util/makeVec.hpp)
• project() (タプルのコンテナの第 I 要素を抽出したvectorを返す) (Util/project.hpp)
• randoms (randint()とかchoice()とか) (Util/randoms.hpp)
• rep()マクロ (Util/rep-macro.hpp)
• runlength() (ランレングス圧縮) (Util/runlength.hpp)
• Timer (実行時間計測) (Util/timer.hpp)
• zip() (n個のvectorからn要素のタプルのvectorを生成する) (Util/zip.hpp)

export

• export/template-prototype.cpp
• all()マクロ (export/template.cpp)

short-snip

• short-snip/bye.cpp
• short-snip/div-ceil.cpp
• short-snip/io-setup.cpp
• short-snip/possible.cpp
• short-snip/precision.cpp
• short-snip/sigma.cpp
• short-snip/sqr.cpp
• short-snip/uniq.cpp
• short-snip/yay.cpp
• short-snip/yesno.cpp

tool

• tool/gen-codesnippet.py
• tool/gen-snippet.py
• tool/gen-template.py
• tool/progReader.py

Verification Files

test/AOJ

• test/AOJ/0264-Finite-Field-Calculator.test.cpp
• test/AOJ/0558-Cheese.test.cpp
• test/AOJ/1501-Grid.test.cpp
• test/AOJ/ALDS1_11_C-Breadth-First-Search.test.cpp
• test/AOJ/ALDS1_14_B-String-Search.test.cpp
• test/AOJ/ALDS1_1_C-Prime-Numbers.test.cpp
• test/AOJ/DPL_5_A.test.cpp
• test/AOJ/DSL_1_A.test.cpp
• test/AOJ/GRL_1_A-Single-Source-Shortest-Path.test.cpp
• test/AOJ/GRL_2_A-Minimum-Spanning-Tree.test.cpp
• test/AOJ/NTL_1_A-Prime-Factorize.test.cpp
• test/AOJ/NTL_1_B-Power.test.cpp
• test/AOJ/NTL_1_D-Eulers-Phi-Function.test.cpp
• test/AOJ/NTL_1_E-Extended-Euclid-Algorithm.test.cpp

test/helloworld

• test/helloworld/at.test.cpp
• test/helloworld/divisor-count-table.test.cpp
• test/helloworld/eratosthenes-sieve.test.cpp
• test/helloworld/fix-point.test.cpp
• test/helloworld/osa_k.test.cpp
• test/helloworld/project.test.cpp
• test/helloworld/rolling-hash.test.cpp
• test/helloworld/runlength.test.cpp
• test/helloworld/zip.test.cpp

test/yosupo

• test/yosupo/static-range-sum.test.cpp