少しブログを書きたいようにじゃなくて有用な方面にちゃんとしようとおもいました。

黄入記事でも書いたのですが、ライブラリやマクロ作成での恩恵があったので個人的に実装して使用頻度の高いものをリストアップしておきます。ひとまず現ABCの500点が解けるくらいの目安に書いてますので、SCCやMaxFlowあたりも入れたかったのですが省略します。 C++前提にしていますが御愛嬌。

繰り返し二乗法（★★☆）

$x^{N}$ を $O(logN)$ で求める方法。本来は真っ先にModを言いたのだが、そこでこの方法を使うので先に。
例えば $x^{70}$ を求めたい場合は70回かけるのもアリだが、 $x^{2}×x^{4}×x^{64}$ でも十分求まる。
そしてこの $2$ の累乗 $K$ は
$x^{2}=x×x$
$x^{4}=x^{2}×x^{2}$
$x^{8}=x^{4}×x^{4}$
…
$x^{64}=x^{32}×x^{32}$
と $O(logK)$ で求めることができるのである。
実装はシンプルな再帰で十分可能。普通のlong longやdoubleよりも、巨大な数値にも対応できるModの計算や行列計算でよく使うので是非ともテンプレートを利用して実装しておこう。

行列とか型によっては単位元（ $1$ )の定義がバラバラだったりあったりなかったりが面倒なので、私はp=1で切り上げてしまっている。 ACLのmodintにはpowがデフォルト装備なので覚えておきましょう。

template<typename T>
T Power(T var, ll p) {
  if (p == 1) return var;
  T ans = Power(var * var, p / 2);
  if (p & 1) ans *= var;;
  return ans;
}

GCD（★★★）

最小公倍数を求めるもの。C++やPythonは標準装備。代表例としてユークリッド互除法で、細かい説明はたくさん資料があるので省くがお互いをお互いに割った余りを求めていくと、最後には最小公倍数のみが余るというものである。最悪の組み合わせはフィボナッチ数列の隣り合った項だが、それでも $O(loga+logb)$ 。
最大公約数を求める場合は $LCM(a,b)×GCD(a,b)=a×b$ の式を利用しよう。

ll Gcd(ll a, ll b) {
  return b ? Gcd(b, a % b) : a;
}

Mod（★★★）

素数 $P$ で割った余りを求める値ライブラリ。言わずもがな頻出。逐一割り算をさせるとどこかで割り忘れてバグが出かねないので型のひとつとして常に使える状態にしておきましょう。
実装難な部分として割り算。ざっくり言うと割り算の概念は

素数で割った余りでは $a≡0$ でない $a$ に対し $ab≡1$ となる $b$ が存在する
これを逆数として「 $a$ で割る」を「 $b$ でかける」と同等にみなせる
この $b$ を瞬時に見つけ出したい。どちらも計算量は $O(logP)$
⇒フェルマーの小定理と繰り返し二乗法を使う方法
⇒拡張ユークリッド互除法を使った方法

フェルマーの小定理と繰り返し二乗法

$P$ を素数として $a$ を $p$ の倍数でない整数としたとき下記が成り立つ
$a^{P-1}≡1 (mod P)$
つまり $b≡a^{P-2}(mod P)$ とすれば、これは $a$ の逆数になってくれるので、上記の繰り返し二乗法を使えば $O(logP)$ で出る。

拡張ユークリッド互除法

上記のユークリッド互除法を応用した拡張ユークリッド互除法。簡単に言うと $s,t$ が与えられた際に、以下を満たす $x,y$ を求めるというもの
$sx+ty=GCD(s,t)$
で、この $s$ に $a$ を、 $t$ に $P$ を代入すると、GCDは $P$ が素数で1になるので。
$ax+Py=1$
この時の $x$ が逆数 $b$ になってくれるというわけである。ただしこの $x$ と $y$ は一意でないです。 $x$ を $P$ 上げて $y$ を $a$ 下げても解になりますので、後からbは $[0,P)$ の中に収めるようにしましょう。

ではどうやって求めるか。そこで出てくるのが拡張ユークリッド互除法です。
例えば $17x+7y=1$ となるxとyを求めてみたいです。
…と言いつついったん忘れて、ではまずこの $17$ と $7$ のユークリッド互除法をするとどうなるかを見てみましょう。
$(17,7)$
$(3,7)$
$(3, 1)$
$(0,1)$

ではこれと同じ流れを、今度は $x$ と $y$ を添えてみてみましょう
$17x+7y=1$
$3x+7(y+2x)=1$
$3(x+2(y+2x))+1(y+2x)=1$
$0(x+2(y+2x))+1(y+2x+3(x+2(y+2x))=1$

ややこしいですが、どの式も $17x+7y=1$ と同等です。
明確な事として、最後の式右項の $(y+2x+3(x+2(y+2x))=1$ なら絶対この式成り立ちます。

では最後の項の左の項のカッコの中を $X$ 、右の項を $Y$ とすると
$17(X-2(Y-3X)+7(Y-3X-2(X-2(Y-3X))=1$
$3(X-2(Y-3X)+7(Y-3X)=1$
$3X+1(Y-3X)=1$
$0X+1Y=1$

ではここで具体的に $X=0$ と $Y=1$ を入れてみましょう。 $X$ はどんな値でも良いですが、 $0$ だと値が膨らみづらいし楽です。
$17･(-2)+7(1-(-2)･2)=1$
$3(0-2･1)+7･1=1$
$3･0+1･(1-3･0)=1$
$0･0+1･1=1$
こんな形で逆走をすることで $17･(-2)+7･5=1$ が出ます。
ユークリッドの互除法を上から解いた後に、帰りがけにこの逆走をしようと言う算段になります。
先程のGCDのユークリッドの互除法と同じ計算量になるので、最悪でも $O(logP)$ です。

tuple<ll, ll, ll> extGcd(ll a, ll b) {
  if (b == 0) 
    return make_tuple(a, 1, 0);    // 行きがけのゴール地点
  auto [g, x, y] = extGcd(b, a % b);
  return make_tuple(g, y, x - y * (a / b));  // 帰りがけの動作
}

個人的には拡張ユークリッド互除法のほうが早そうな印象です。

追記

と思って調べてみたんですが、簡単に言うと再帰回数だけ見たら「拡張ユークリッド互除法のほうが優れているが思ったほどではなかった」って感じでした。

フェルマーの小定理は累乗が $1000000006$ なので、再帰回数は30回固定です。
対してフェルマーの小定理は $5$ とかの $1000000007$ を一瞬で小さい余りにしてしまう奴らは良いんですが、普通に再帰回数30回超えてる奴らいました。考えてみればフィボナッチ数が $1000000007$ を超えるのは40項からですし、フィボナッチ数の一般項の底は黄金比なのでフェルマーの小定理の底よりも定数倍重いので、30を超えるのは結構自然なことでした。

35
79613267, 178266627, 367168637, 379817954, 379836910, 379864965, 381457740, 381871686, 381917109, 381966026, 387570057, 393567101, 419821296, 435599564, 549392382
36
564400443, 580178711, 606432906, 612429950, 618033981, 618082898, 618128321, 618542267, 620135042, 620163097, 620182053, 632831370, 821733380, 920386740,

平均すると $17.932$ 回程度だったので一応ユークリッド互除法の方が優れてますねと言ってもいいんじゃないですかね。大差ない気しかしない。

これを最悪っぽい $920386740$ のケースで超雑な調べ方で $10^{7}$ 回分くらい計測した感じ

拡張ユークリッドの互除法：4121ms
フェルマーの小定理：3129ms

逆にユークリッドの互除法が圧勝する $2$ でやると

拡張ユークリッドの互除法：276ms
フェルマーの小定理：3185ms

概ね再帰回数に従った動きをしてくれていますね。
ご覧の通り最悪ケースは結構大きな値になりますので、期待値で考えても「微妙な差で負けたくない！」というのであれば拡張ユークリッドの互除法を使うと良さそうだと思います。あと「 $2$ で割る」「階乗で割る」などの何度も使うことになりそうな逆数に関しては、あらかじめ逆数を求めておくと軽い削減になるかも。

階乗・コンビネーション（★★★）

頻出。「 $N$ 個から $M$ 個選ぶコンビネーションを当然のように聞いてくる問題がわりとある。
$_NC_M={\dfrac {N!}{M!(N-M)!}}$
これが成り立つので、あらかじめ階乗を求めておけば一瞬で求められる。階乗を事前計算しておこう。やはり値は大きくなりやすくModとの組み合わせられるように。
$N$ がやたら大きくて $M$ がやたら小さい場合は、階乗ではなくて公式をしっかり使おう。

template<typename T>
void Factorical(ll siz, vector<T>& out) {
  out.resize(siz + 1);
  out[0] = T(1);
  for (ll i = 0; i < siz; i++) 
    out[i + 1] = out[i] * (i + 1);
}

template<typename T>
T Combi(ll a, ll b, vector<T>& fact) {
  return fact[a] / (fact[b] * fact[a - b]);
}

Dijkstra法（★★★）

最短経路を求める方法のひとつ。他にもBellmanfordとWarshallFloydがありますが、Dijkstraが計算量で圧倒的に勝っていますので頻出です。ここまでのものと比べて実装は重いですがしっかりやっておきましょう。
他2つとの大きな違いは下記記事K問題でもざっくり言いましたが、それぞれの強みが下記な感じです。

【AtCoder】第7回アルゴリズム検定振り返り - あめんばーどのバーチャル日記

BellmanFordは負の閉路探知ができる
WarshallFloydは最も遅いが全ての点からの最短経路距離を求められる。負の閉路探知もできる。実装が楽。

Dijkstraは負の閉路があると無限に終わりません。閉路じゃなくても負の道があるだけで爆発します。負の辺がある場合はBellmanFordを使うか、何かしらで負の辺をなくす工夫をする印象です。だいたい後者。高速な計算量にしたい場合は優先度付きキュー（PriorityQueue）を持つことが前提になりますが.NET6にもPriorityQueueが入ったようですね。

最初にスタート地点を距離0として優先度付きキューに入れる
優先度付きキューの中で最も距離の短い点を選択する
その点からの移動先で、最短距離を更新できる場所を更新しキューに入れる
キューの中身がなくなるまで繰り返す

ポイントは残っている最も短い距離の点を選ぶ事と負辺がないという前提により、選ばれた点がこれ以上短くなることが保証されている点です。
だからこそ選択された点はもう二度と選ばれることがないので、この繰り返しは $V$ 点 $E$ 辺あるとしたら高々 $V$ 回までしか行われません。
ただし移動先をキューに入れる動作は $E$ 回行われ、優先度付きキュー操作は毎回 $O(logN)$ かかりますので $O((V+E)logV)$ となる。

ついでなんですが、値を更新した時に「どの点から移動した時に値を更新したのか」を記憶しておくと経路復元ができます。
ポテンシャルとか牛ゲーとか頂点の種類増加とかとにかく応用の幅が広いので、動き方はしっかり理解しておくといいでしょう。

class Dijkstra {
public:

  Dijkstra(ll n) {
    size = n;
    edges.resize(n);
    dist.resize(n);
    rev.resize(n);
  }
  // ---注：有向---
  void addEdge(ll from, ll to, ll cost = 0) {
    edges[from].push_back({ to,cost });
  }

  void CalcDist(ll s) {
    dist.assign(size, LLONG_MAX);
    rev.assign(size, -1);
    dist[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
      P p = que.top();
      que.pop();
      ll v = p.second;
      if (dist[v] < p.first) continue;
      for (auto& e : edges[v]) {
        if (dist[e.to] <= dist[v] + e.cost) continue;
        dist[e.to] = dist[v] + e.cost;
        rev[e.to] = v;
        que.push(P(dist[e.to], e.to));
      }
    }
  }

  // 基本データ

  ll size;  // 点数
  struct edge { ll to, cost; };
  typedef pair<ll, ll> P;
  priority_queue<P, vector<P>, greater<P>> que;
  vector<vector<edge>> edges;
  vector<ll> dist;
  vector<ll> rev;
};

UnionFind・最小全域木（★★★・★☆☆）

400点でも出ることのあるUnionFindです。貨物列車しゅっしゅっしゅ。
最小全域木は求める方法がPrim法とKruskal法があるのですが、私はUnionFindとセットで使えるKruskal法にしてます。今のところ大きな違いに遭遇したことはありません。情報求。

UnionFindはざっくり言うとこうです。

全ての頂点が自分の頂点を親として持つ
ある二つの頂点を同じグループに所属させる場合、どちらかをどちらかの親にする
一番上の親（自分の頂点が親）が同じもの同士だったら、同じグループにいる

という判定のもの。さらに下記のようにすると早くなる。具体的にはアッカーマン関数の逆関数で、雑に言うと $logN$ がかわいく見えてくるレベルのほぼ定数。

どちらかをどちらかの親にするのは、ある二つの頂点ではなくその二つの頂点の一番上の親同士でさせる
さらにどちらが親になるかは自分の子供の個数が大きい方にさせる
一度自分の一番祖先の親が判明した場合、自分の親をその一番祖先に変更して次回からショートカットできるようにする

UnionFindのグループのサイズを聞く問題があるので、サイズの管理はできるようにしておきましょう。

Kruskal法については今回は省略します。

class UnionFind {
public:

  UnionFind(ll num) {
    parent.resize(num);
    size.assign(num,1);

    for (ll i = 0; i < num; i++)
      parent[i] = i;
  }

  ll GetRoot(ll leaf) {
    if (parent[leaf] == leaf) return leaf;
    return parent[leaf] = GetRoot(parent[leaf]);
  }

  void Union(ll a, ll b)
  {
    ll ra = GetRoot(a);
    ll rb = GetRoot(b);
    if (ra == rb) return;
    if (size[ra] < size[rb]) swap(ra, rb);
    size[ra] += size[rb];
    parent[rb] = ra;
  }

  bool SameUnion(ll a, ll b) {
    return GetRoot(a) == GetRoot(b);
  }

  vector<ll> parent;
  vector<ll> size;   // only root
};

セグ木、BIT（★★☆）

高度ですが優先度は高いと思います。BITは限定的な場面でセグ木の代用ができるものですが、実装や速度が軽い上にそこそこの頻度で出てくる転倒数の計算で強いのでオススメです。理解には苦しむけど武器の一つとして写経でも全然いい気がします。

セグ木に関してはこちらのL問題で細かいことを書いてますので、よかったらご覧ください。

【AtCoder】第7回アルゴリズム検定振り返り - あめんばーどのバーチャル日記

セグ木のコードについてはすいません。今見直したらなんか間違えている疑惑がある個所があったのでまた今度。 BITは蟻本にもあるし探せば30行くらいのがサクッと見つかる超シンプルなコードなので、他にお任せします。

よくつかうマクロたち

細かいけどよくやる操作で導入したらいろいろとミスが減ったもの。だいたいがtatyamさんのコードを見て拝借した者である。強い人のコードは見てなんぼです。

for文略（★★★）

めっちゃ使う。可読性向上にも繋がった。最高。

#define FOR(i, a, b) for(ll i=(a); i<(b);i++)
#define REP(i, n) for(ll i=0; i<(n);i++)
#define ROF(i, a, b) for(ll i=(b-1); i>=(a);i--)
#define PER(i, n) for(ll i=n-1; i>=0;i--)

long long・long longのvector・make_pair・modint998244353/1000000007、long long(0)の略（★★★）

とてもよく使う。書きづらい頻出型はもう全部潰す。

using ll = long long;
#define VL vector<ll>
#define VVL vector< vector<ll> >
using mint = modint1000000007;
using mint2 = modint998244353;

最大化、最小化（★★★）

最大値や最小値を更新。自分でも何か作ろうとしたら地味に頻度が高い。

#define TOMAX(n,v) n=n<v?v:n
#define TOMIN(n,v) n=n>v?v:n

all、ソート（★★☆）

ソート頻度が非常に高く、毎回begin,endを書くのが非常に面倒だったのが解決

#define all(i) begin(i),end(i)
#define SORT(i) sort(all(i))

ビット操作（★☆☆）

これだけやたら使った#define EXISTBIT(x,i) (((x>>i) & 1) != 0)

配列読込（★★☆）

どなたから拝借したか忘れてしまいましたマジでごめんなさい。けど超速で配列が読み込めるのとても強いです。

template<typename T = ll>
vector<T> read(size_t n) {
  vector<T> ts(n);
  for (size_t i = 0; i < n; i++) cin >> ts[i];
  return ts;
}

さいごに

verifyはしておこう。Dijkstraのライブラリを組んでコンテスト本番で間違えてたことに気づくとか、暖色コーダーになってはじめてUnionFindがずっとバグってるのに気づいた人がいたそうですので。あめんばーって言う人らしい。

強い人のコードはいっぱい見よう。わけがわかんなかったらわけがわかるように頑張るかわけがわかる強い人のコードをいっぱい見よう。

それではまた。

2022/08/07追記やたら直したい部分が目に留まったので再修正しました

あめんばーどのバーチャル日記

バーチャルな世界で過ごして競プロしてる人の雑談

【競プロ】個人的に優先度の高いライブラリ