文字列検索の計算量を減らしたいときに使われるアルゴリズムの一覧です。といっても、2019/07/29現在はローリングハッシュのみです。随時追加していきます。【2019/07/30追記】Z AlgorithmとKMP法と接尾辞配列の項目を追加しました。 文字列\(S\)に部分文字…

yukicoder.me 考察 この問題は、「合計が\(X\)以下となる\(0\)以上の整数\(D-1\)個の組はいくつあるか」という問題に言い換えられます。そしてこの問題はベル数やスターリング数を求めるときのように、漸化式を立てることで数え上げることができます。 実装 …

yukicoder.me 概要 以下の条件を満たす数列\((A_1, \ldots, A_N)\)は何通りあるでしょうか。\(10 ^ 9 + 7\)で割った余りを求めてください。 \(A_1 + \ldots + A_N = S\) 任意の\(i(1 \le i \le N - 1)\)に対して\(A_i + K \le A_{i + 1}\) 制約：\(2 \le N \…

Link-Cut Treeについてのメモです。 回転操作を行っても、左右の位置関係の情報は失われない 最初は、回転操作を行うと左右の位置関係の情報は失われると思っていました。Link-Cut Treeの仕組みの理解を妨げていた最大の誤解です。平衡二分探索木で回転操作…

atcoder.jp 概要 \(N\)頂点\(M\)辺の単純な無向グラフがあります。以下のクエリが\(Q\)個与えられるので答えてください。 頂点\(A, B, C\)について、同じ辺を2度通らないパス\(A\)→\(B\)→\(C\)は存在するか 制約：\(3 \le N \le 10 ^ 5\)、\(1 \le M \le 2 \…

木DPを使って解ける問題には、以下のものがあります。 ある頂点から最も遠い頂点までの距離はいくつか ある頂点を根としたときの木の深さはいくつか これらの問題に共通していることは、「ある頂点」という文言が含まれていることです。頂点数を\(N\)とおい…

LCAを求める方法はいくつかありますが、今回はダブリングを使う方法とHL分解（Heavy Light Decomposition）を使う方法を紹介します。【追記】オイラーツアーを使う方法を追加しました。【追記】Link-Cut Treeを使う方法を追加しました。 ダブリングによる実…