7K12 blog

猫でも分かるアルゴリズム解説

2022-03-01から1ヶ月間の記事一覧

NyaaLIB::NT_TwelvefoldWay

写像12相ライブラリ ただし写像12相以外の組み合わせ計算も含む Pow(x, n): 繰り返し二乗法 P(n, r): 順列 C(n, r): 組み合わせ H(n, r): 重複組み合わせ IEP(n, r): 包除原理 Stirling(n, r): 第二種スターリング数 Catalan(n): カタラン数 #include <bits/stdc++.h> names</bits/stdc++.h>…

NyaaLIB::GTL_Kruskal

クラスカル法 重み付き連結グラフの最小全域木を求める 引数 ARG_Kruskal n: 頂点数 g: 重み付き隣接リスト 戻り値 最小全域木となる辺 {from, to, cost} の集合を返す 依存クラス DS_UnionFind https://9871225.hatenablog.com/entry/2022/03/02/202403 #in…

NyaaLIB::DS_UnionFind

Union Find DS_UnionFind(n): 半開区間[0,n) のデータ構造を確保 以下で処理できる関数 Union(x, y): xとyを結合 Find(x): xの根を返す Max(x): xが属する集合の最大値を取得 Min(x): xが属する集合の最小値を取得 Same(x, y): xとyが同じ集合どうか判定 Siz…

NyaaLIB::NT_ModINT

MOD 型ライブラリ #include <bits/stdc++.h> namespace NyaaLIB { /** * MOD 型ライブラリ **/ template <long long mod> struct NT_ModINT { // 非型テンプレートパラメータ using mint = NT_ModINT; using ll = long long; ll x; NT_ModINT() : x(0) {} NT_ModINT(ll init) : x(init% mod</long></bits/stdc++.h>…