数学剰余, 二項係数, 動的計画法, Lucasの定理, 素数の剰余

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さい場合は十分高速です。

Lucas の定理

任 ...

2020年3月21日数学最大公約数, 配列, 結合則

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。

例:

Input: A = {36, 12, 48}

数学最大公約数, ユークリッドの互除法, 拡張ユークリッドの互除法, 1次方程式

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求 ...

2020年3月20日数学最小公倍数, 配列, 結合則

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。

Input: a = {1, ...

2020年3月20日グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, Union-Find, 連結成分のサイズ, 同じ連結成分か判定

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, 連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

2020年3月20日その他区間和, 区間, 累積和, 配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間

累積和の気持ち累積和とは

累積和は、「始めから i 番目までの和を前処理で計算したもの」です

2020年3月20日その他

大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...

グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理, カット, 最小カット

アルゴリズム

最小カットの容量を求めるアルゴリズム:

フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
\(|f^*|\) が最小カットの容量

...

グラフ競プロ, フロー, 最大フロー, 二部グラフ, 最大マッチング, マッチング

アルゴリズム

二部グラフの最大マッチングを求めるアルゴリズム:

二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る\(G\) にソース \(s\) ...