7K12B 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…

mod型ライブラリ LIB::NT_ModINT

template<class T1, class T2>static mint Pow(T1 x, T2 n) 繰り返し二乗法で を計算する 計算量 namespace LIB { template<long long mod>class ModINT { using mint=ModINT; using ll=long long; ll inv(ll a, ll m) { ll b=m,u=1,v=0; while(b) { ll t=a/b; a-=t*b,swap(a,b); u-=t*v,swap(u,</long></class>…