【競技プログラミング】目指せ全完！！！yosupo judgeの解説記事まとめ

# はじめに
[yosupo judge](https://judge.yosupo.jp/)
データ構造やアルゴリズムが沢山集まる場所ですが、どうしてもハードルが高いので、初心者でも取っ掛かりやすいようにまとめます
間違いがあったり追加してほしい記事があれば[twitter](https://twitter.com/hotmanww)まで報告してくれると嬉しいです(Qiitaのプルリクでもいいです)

テストケースを見たい方はこちらを参考にしてください
[yosupo judgeのテストケースを見る方法](https://hotman78.hatenablog.com/entry/2020/06/18/085018)

# 目次
[Sample](#sample)
[Data Structure](#data-structure)
[Graph](#graph)
[Tree](#tree)
[Math](#math)
[Convolution](#convolution)
[Polynomial](#polynomial)
[Matrix](#matrix)
[String](#string)

# Sample
### [A + B](https://judge.yosupo.jp/problem/aplusb)
[APG4b](https://atcoder.jp/contests/APG4b)
### [Many A + B](https://judge.yosupo.jp/problem/many_aplusb)
[fastIO(Codeforces)](https://codeforces.com/blog/entry/8080)
[高速I/O処理 - yaketake08's 実装メモ](https://tjkendev.github.io/procon-library/cpp/template/fast_io.html)

# Data Structure
### [Associative Array](https://judge.yosupo.jp/problem/associative_array)
恐らくfixed universe problemの高速処理のverify用？
[Trie for Fixed Universe Set -週刊 spaghetti_source](https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20121216/1355652855.html)
hash tableのverifyな気もしてきた
[ハッシュテーブル - wikipedia](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB)
### [Predecessor Problem](https://judge.yosupo.jp/problem/predecessor_problem)
恐らく VEBTree 想定です
[謎木速いけど微妙にバｇ・・・バグらないだと！？ - 赤い黒歴史を蓄積する](https://catupper.hatenablog.com/entry/20120830/1346338855)

### [Unionfind](https://judge.yosupo.jp/problem/unionfind)
[Union-Find木の解説と例題 - Qiita](https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396)
Union-Findは木じゃない٩(๑`^´๑)۶

### [Static Range Sum](https://judge.yosupo.jp/problem/static_range_sum)
累積和でもBITでもセグメント木でもなんでもいい
[累積和を何も考えずに書けるようにする！
 -Qiita](https://qiita.com/drken/items/56a6b68edef8fc605821)

### [Static RMQ](https://judge.yosupo.jp/problem/staticrmq)
[Sparse Tableを知ったので、忘れないように。 - tookunn's diary](http://tookunn.hatenablog.com/entry/2016/07/13/211148)
[Disjoint Sparse Table と セグ木に関するポエム - noshi91のメモ](http://noshi91.hatenablog.com/entry/2018/05/08/183946)
[構築 O(N) クエリ O(1) の RMQ - noshi91のメモ](http://noshi91.hatenablog.com/entry/2018/08/16/125415)
[前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ](http://joisino.hatenablog.com/entry/2017/08/13/210000)
同じ$\<O(N),O(1)\>$でもアプローチが違います
[Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing.(Codeforces)](https://codeforces.com/blog/entry/57046)
$\<O(N\log \log N),O(1)\>$のsparse tableの上位互換です

### [Point Add Range Sum](https://judge.yosupo.jp/problem/point_add_range_sum)
[セグメント木をソラで書きたいあなたに](http://tsutaj.hatenablog.com/entry/2017/03/29/204841)
セグメント木とかで調べればいくらでも出てきます

### [Point Set Range Composite](https://judge.yosupo.jp/problem/point_set_range_composite)
[データ構造と代数構造 - koba-e964の日記](http://koba-e964.hatenablog.com/entry/2016/12/14/214132)
[セグ木に載せるモノイドまとめ（未完） - beet's soil](http://beet-aizu.hatenablog.com/entry/2019/03/12/171221)
要するに可換性を要求しないように注意深くセグメント木を実装しましょうねという話です(非再帰なら要注意)

### [Range Affine Range Sum](https://judge.yosupo.jp/problem/range_affine_range_sum)
[遅延評価セグメント木をソラで書きたいあなたに - hogecoder](http://tsutaj.hatenablog.com/entry/2017/03/30/224339)

### [Range Chmin Chmax Add Range Sum](https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum)
[Segment Tree Beatsの実装メモ (基本まわり)](https://smijake3.hatenablog.com/entry/2019/04/28/021457)
[Segment Tree Beatsの実装メモ (応用的な例題まわり)](https://smijake3.hatenablog.com/entry/2019/05/18/145531)

### [Range Kth Smallest](https://judge.yosupo.jp/problem/range_kth_smallest)
[WaveletMatrix で快適な整数列ライフを送ろう](http://noshi91.hatenablog.com/entry/2018/06/19/192741)

### [Vertex Add Path Sum](https://judge.yosupo.jp/problem/vertex_add_path_sum)
[Easiest HLD with subtree queries(codeforces)](https://codeforces.com/blog/entry/53170)
[Heavy-Light Decomposition - beet's soil](http://beet-aizu.hatenablog.com/entry/2017/12/12/235950)
[2種類のEuler Tourについて - beet's soil](http://beet-aizu.hatenablog.com/entry/2019/07/08/174727)
オイラーツアーでも解けますがHL分解がおすすめ

### [Vertex Set Path Composite](https://judge.yosupo.jp/problem/vertex_set_path_composite)
同上(向きに気をつけて)(僕はLC木で通しました(後述))

### [Vertex Add Subtree Sum](https://judge.yosupo.jp/problem/vertex_add_subtree_sum)
同上

### [Dynamic Tree Vertex Add Path Sum](https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum)
[Link-Cut 木 - ei1333の日記](https://ei1333.hateblo.jp/entry/2018/05/29/011140)
[Link-Cut Treeの実装メモ - 日々drdrする人のメモ](https://smijake3.hatenablog.com/entry/2018/11/19/085919)
[プログラミングコンテストでのデータ構造 2 ～動的木編～](https://www.slideshare.net/iwiwi/2-12188845)

### [Dynamic Tree Vertex Set Path Composite](https://judge.yosupo.jp/problem/dynamic_tree_vertex_set_path_composite)
同上

### [Dynamic Tree Vertex Add Subtree Sum](https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_subtree_sum)
同上+[Link Cut Treeで部分木の情報を管理する - beet's soil](http://beet-aizu.hatenablog.com/entry/2019/06/08/221833)

[Toptree 導入編 - niuez’s diary](https://niuez.hatenablog.com/entry/2019/08/04/191420)
[Toptree - Link & Cut編 - niuez’s diary](https://niuez.hatenablog.com/entry/2019/08/05/114511)
[top tree 概要 - noshi91のメモ](http://noshi91.hatenablog.com/entry/2019/08/05/175545)
TopTreeでも解けます(部分木の情報を管理するLink Cut Tree と TopTree は本質的には同質)

[【競技プログラミング】online dynamic connectivity(削除可能union-find)の作り方を詳しく解説！！！](https://qiita.com/hotman78/items/78cd3aa50b05a57738d4)
オイラーツアーツリーでも解けます

### [Dynamic Tree Subtree Add Subtree Sum](https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum)
同上


### [Set Xor-Min](https://judge.yosupo.jp/problem/set_xor_min)
[非負整数値を扱う Trie について -kazuma8128’s blog](https://kazuma8128.hatenablog.com/entry/2018/05/06/022654)

### [Line Add Get Min](https://judge.yosupo.jp/problem/line_add_get_min)
[Li Chao Treeのメモ - 日々ｄｒｄｒする人のメ](https://smijake3.hatenablog.com/entry/2018/06/16/144548)

### [Segment Add Get Min](https://judge.yosupo.jp/problem/segment_add_get_min)
同上

### [Queue Operate All Composite](https://judge.yosupo.jp/problem/queue_operate_all_composite)
[Sliding Window Aggregation](https://scrapbox.io/data-structures/Sliding_Window_Aggregation)

### [Static Range Frequency](https://judge.yosupo.jp/problem/static_range_frequency)
[WaveletMatrix で快適な整数列ライフを送ろう](http://noshi91.hatenablog.com/entry/2018/06/19/192741)
単に集合を管理するデータ構造を用いた平面操作をすることでも解けます。

### [Static Range Inversions Query](https://judge.yosupo.jp/problem/static_range_inversions_query)
恐らく平方分割より計算量が落ちることはないです
[伝家の宝刀　クエリ平方分割について - 思考の墓場](https://sigma1113.hatenablog.com/entry/2020/12/15/225256)
[平方分割の練習をしようにも難しい問題ばかり、そんなお悩みに狙いを決めて手取り足取りのレクチャーです！ - CADDi ENGENEER Tech Blog](https://caddi.tech/archives/1259)
### [Rectangle Sum](https://judge.yosupo.jp/problem/rectangle_sum)
[セグメントツリーにセグメントツリーを乗せる手法（2Dセグメントツリー）- はまやんはまやんはまやん](https://www.hamayanhamayan.com/entry/2017/12/09/015937)
[ちょっと変わったセグメント木の使い方 - ei1333の日記](https://ei1333.hateblo.jp/entry/2017/12/14/000000)
[WaveletMatrix で快適な整数列ライフを送ろう](http://noshi91.hatenablog.com/entry/2018/06/19/192741)
[つくってなぐろ (永続配列/永続Union-Find木/永続セグメント木の作り方と意義、具体例)](https://qiita.com/hotman78/items/9c643feae1de087e6fc5)

### [Point Add Rectangle Sum](https://judge.yosupo.jp/problem/point_add_rectangle_sum)
[セグメントツリーにセグメントツリーを乗せる手法（2Dセグメントツリー）- はまやんはまやんはまやん](https://www.hamayanhamayan.com/entry/2017/12/09/015937)

### [Persistent Queue](https://judge.yosupo.jp/problem/persistent_queue)
[data-structures - scrapbox](https://scrapbox.io/data-structures/Contents)
[Purely Functional Data Structures(英語)](https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf)
$O(Q)$があります(よくわからない)
[Re永続データ構造が分からない人のためのスライド](https://www.slideshare.net/qnighy/re-15443018)
ここに出てくる木のダブリングでも出来ます(意外と速いらしいです)
[つくってなぐろ (永続配列/永続Union-Find木/永続セグメント木の作り方と意義、具体例)](https://qiita.com/hotman78/items/9c643feae1de087e6fc5)
取り敢えず永続配列持ってれば配列でqueueを作るあれが出来ます
stack2つでqueueを作るやつは償却計算量で抑えられているので普通にやると死にます

### [Persistent UnionFind](https://judge.yosupo.jp/problem/persistent_unionfind)
多分部分永続だと無理(だよね？)で全永続UFが必要っぽい
永続配列使ってUFするのが一番ラクそう
[部分永続Union-Findの実装 -Mister雑記](https://misteer.hatenablog.com/entry/persistentUF)
[つくってなぐろ (永続配列/永続Union-Find木/永続セグメント木の作り方と意義、具体例) -Qiita](https://qiita.com/hotman78/items/9c643feae1de087e6fc5)

# Graph
### [Cycle Detection](https://judge.yosupo.jp/problem/cycle_detection)
[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】-Qiita](https://qiita.com/drken/items/a803d4fc4a727e02f7ba)

### [Shortest Path](https://judge.yosupo.jp/problem/shortest_path)
負辺なしの最短経路はダイクストラ、今回は復元もいるらしい
復元は一般のDPに関する物を貼ったがダイクストラもDPなのでそのまま適用出来る
[ダイクストラ法 - ソフトウェア科学研究室](http://www.ss.cs.meiji.ac.jp/CCP024.html)
[意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法 -Qiita](https://qiita.com/drken/items/0c7bab0384438f285f93)

### [Strongly Connected Components](https://judge.yosupo.jp/problem/scc)
[強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語](https://mathtrain.jp/kyorenketsu)

### [K-Shortest Walk](https://judge.yosupo.jp/problem/k_shortest_walk)
[Finding the k Shortest Paths (SICOMP'98)-(iwi) 備忘録](http://iwiwi.hatenadiary.jp/entry/2013/12/26/001253)
[Eppstein's Algorithm (Find the K shortest paths) 解説と実装 (Python)-Qiita](https://qiita.com/nariaki3551/items/0ab83541814f98eab322)
[K-最短路をO((V+E)logV+KlogK)で！？Eppstein's Algorithmのわかりやすい解説！！！【C++実装つき】-Qiita](https://qiita.com/hotman78/items/42534a01c4bd05ed5e1e)
自作問題

### [Two-Edge-Connected Components](https://judge.yosupo.jp/problem/two_edge_connected_components)
[橋・二重辺連結成分分解 - あったこといろいろ - id:Yazaten](http://yazaten.hatenablog.com/entry/2016/12/05/094725)

### [Three-Edge-Connected Components](https://judge.yosupo.jp/problem/three_edge_connected_components)
~~わからない(確信がない)です(は？)~~
~~作問者しかACしてないので多少はね？~~
~~近々解いて書きます(本当ですか？)~~
[A simple 3-edge connected component algorithm revisited](https://www.sciencedirect.com/science/article/abs/pii/S0020019013002470)
作問者はこれを見て作ったそうです(有料です)(noshi91さんありがとうございます)

### [Minimum cost b-flow](https://judge.yosupo.jp/problem/min_cost_b_flow)
[ぼくの考えたさいきょうのフローライブラリ - ](https://misawa.github.io/others/flow/library_design.html)
色々ある(作問者のみさわさんの発信を見て作るのが良さそう)
ACするだけならPrimal-Dualでもいいかも(間に合うかは知らない)

### [Matching on Bipartite Graph](https://judge.yosupo.jp/problem/bipartitematching)
[二部グラフの最大マッチングと増加道 | 高校数学の美しい物語](https://mathtrain.jp/bipartitematching)
[‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬](https://qiita.com/drken/items/e805e3f514acceb87602)

### [Matching on General Graph](https://judge.yosupo.jp/problem/general_matching)
[GabowのEdmonds' Algorithm(一般マッチング O(VElogV))の解説と実装](https://qiita.com/Kutimoti_T/items/5b579773e0a24d650bdf)

### [Edge Coloring of Bipartite Graph](https://judge.yosupo.jp/problem/bipartite_edge_coloring)
[二部グラフの辺彩色 - ei1333の日記](https://ei1333.hateblo.jp/entry/2020/08/25/015955)
シンプルで面白い

### [Assignment Problem](https://judge.yosupo.jp/problem/assignment)
強烈なテストケースアップデートにより、最小費用流で通すのが難しくなりました。
O(V^3)の特化アルゴリズムである、ハンガリアン法で通すのがおすすめです(逆に速い最小費用流のverifyにも使えます)(僕はcost-scalingで無理やり通しました)
[割当問題のハンガリアン法をpythonで実装してみた -Qiita](https://qiita.com/m__k/items/8e2cb9067ec5d720c30d)
[‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬](https://qiita.com/drken/items/e805e3f514acceb87602)

### [Directed MST](https://judge.yosupo.jp/problem/directedmst)
[最小全域有向木（m log n） - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ](http://joisino.hatenablog.com/entry/2017/01/11/230141)
[最小有向全域木を求める | Chu-Liu/Edmonds' algorithm - Ark's Blog](https://ark4rk.hatenablog.com/entry/2017/09/15/011937)

### [Manhattan MST](https://judge.yosupo.jp/problem/manhattanmst)
[Manhattan Minimum Spanning Tree - 霧でも食ってろ](https://knuu.github.io/manhattan_mst.html)

### [Dominator Tree](https://judge.yosupo.jp/problem/dominatortree)
理解を放棄してACだけなら比較的簡単かも(graphのヤバの中では)
[Dominator Tree - sigma425のブログ](http://sigma425.hatenablog.com/entry/2015/12/25/224053)

### [Maximum Independent Set](https://judge.yosupo.jp/problem/maximum_independent_set)
素直な高速化をすると通る。非常に教育的な高度典型の一つ。
[指数時間アルゴリズム入門 - SlideShare](https://www.slideshare.net/wata_orz/ss-12131479)

### [Chromatic Number](https://judge.yosupo.jp/problem/chromatic_number)
subset convolutionがいると思いきや実は要らない(別に同じ頂点を複数色で塗ってもいいので)
[グラフの彩色数求値 $O(2^n n)$ や$O(2^n)を定数倍高速化したもの - Mathenachia](https://www.mathenachia.blog/chromatic-fast/)
あまりにも賢い解法

### [Enumerate Triangles](https://judge.yosupo.jp/problem/enumerate_triangles)
これとてもおもしろい、最大次数√2MのDAGを作って考えるテクは他にも使えそう
[Trianguler - SlideShare](https://www.slideshare.net/catupper/trianguler)

### [Tree Decomposition (width 2)](https://judge.yosupo.jp/problem/tree_decomposition_width_2)
うしさんがブログに書いた事で少し有名になった概念
グラフを木に変えて木DP出来たりするらしい
本問は連結では無いので、下の手順で森にした後UFやらで適当に繋げる必要がある
うしさんの記事では辺の貼り方がわからないという方にはさてもちブログさんが詳しい
[木幅が2以下のグラフの木分解と動的計画法 - ei1333の日記](https://ei1333.hateblo.jp/entry/2020/02/12/150319)
[木分解を眺める: 最小三角化 PEO 計画 - さてもちブログ](http://satemochi.blog.fc2.com/blog-entry-82.html)

### [Global Minimum Cut of Dynamic Star Augmented Graph](https://judge.yosupo.jp/problem/global_minimum_cut_of_dynamic_star_augmented_graph)
[Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex - researchgate](https://www.researchgate.net/publication/31343031_Computing_a_Minimum_Cut_in_a_Graph_with_Dynamic_Edges_Incident_to_a_Designated_Vertex)
[Minimizing Symmetric Submodular Functions - Slide(Satoru Iwata)](http://www.iasi.cnr.it/~ventura/Cargese13/Lectures%20slides/Iwata4.pdf)

extreme vertex set を求めて木上でHL分解&セグ木 $\mathcal{O}(N^2logN+NM+Q(\log N)^2)$ が想定
最小全域カットを部分問題に含むのでそちらを先に履修するのも手かも
[全域最小カット (Stoer-Wagner Algorithm) - 実装メモ (Python)](https://tjkendev.github.io/procon-library/python/graph/stoer-wagner-algorithm.html)
[乱択アルゴリズム紹介(最小カット) - Preferred Networks Resarch & Development]()

### [Chordal Graph Recognition](https://judge.yosupo.jp/problem/chordal_graph_recognition)
[辞書順幅優先探索Lex BFS（Chordal Graph 5回）- kazu0x17’s diary](https://chocobaby-aporo.hatenablog.com/entry/2018/12/25/011447)
[Chordal Graph: Maximum Cardinality Search - kazu0x17’s diary](https://chocobaby-aporo.hatenablog.com/entry/2017/11/12/094759)
[グラフ探索アルゴリズムとその応用 - Slide](http://hos.ac/slides/20110504_graph.pdf)
最初の方に選んだ頂点に隣接する頂点を優先するLexBFSと呼ばれるBFSを使用する

# Tree

### [Tree Diameter](https://judge.yosupo.jp/problem/tree_diameter)
二回DFSするだけの簡単なお仕事
[木の直径を求める](https://qiita.com/nomikura/items/a4c5be6c72ce854d7ce4)

### [Lowest Common Ancestor](https://judge.yosupo.jp/problem/lca)
[Lowest Common Ancestor(yukicoder)](https://yukicoder.me/wiki/lowest_common_ancestor)

### [Cartesian Tree](https://judge.yosupo.jp/problem/cartesian_tree)
$\lt O(N),O(1)\gt$RMQとかに使えるけど、使いみちは良くわからん(とか言ってたら神記事ができてた)
[前処理O(n)クエリO(1)のLCAと静的RMQ - ｼﾞｮｲｼﾞｮｲｼﾞｮｲ](http://joisino.hatenablog.com/entry/2017/08/13/210000)
[Cartesian tree -wikipedia(en)](https://en.wikipedia.org/wiki/Cartesian_tree)
[列を最小値で分割して再帰するパターンと Cartesian tree ](https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/)
実装法では無いですがいい記事なので

### [Frequency Table of Tree Distance](https://judge.yosupo.jp/problem/frequency_table_of_tree_distance)
重心分解して重心をまたぐ2点に付いてFFTで畳み込む。~~やりたくないでござる。~~
[ツリーの重心分解 (木の重心分解) の図解 -Qiita](https://qiita.com/drken/items/4b4c3f1824339b090202)
[FFT（高速フーリエ変換）を完全に理解する話 -Qiita](https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79)



# Math
### [Counting Primes](https://judge.yosupo.jp/problem/counting_primes)
$O(N^{3/4})$とか$O(N^{2/3})$とかで出来るらしい
Meissel-Lehmer algorithmの軽い説明をすると
合成数は$N^{1/3}$以下の素数の倍数と$N^{1/3}$以上$N^{1/2}$以下の素数を２つかけたものの２つなので、両者の集合を$A$,$B$として$\overline{A}$と$\overline{A}\cap B$を頑張って求める
[N以下の素数の個数 - メモ](http://sugarknri.hatenablog.com/entry/2019/07/31/102422)
[Sum of Multiplicative Function - memo](https://min-25.hatenablog.com/entry/2018/11/11/172216)
[Meissel–Lehmer algorithm -wikipedia](https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm)

### [Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)
[エラトステネスの篩の高速化(全６章)](https://qiita.com/peria/items/a4ff4ddb3336f7b81d50)
[Sieve of Eratosthenes Having Linear Time Complexity(英語)](https://cp-algorithms.com/algebra/prime-sieve-linear.html)

### [Factorize](https://judge.yosupo.jp/problem/factorize)
[素因数分解の高速なアルゴリズム（ロー法） | 高校数学の美しい物語](https://mathtrain.jp/rhoalgorithm)
[ミラー–ラビン素数判定法 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95)

### [Binomial Coefficient](https://judge.yosupo.jp/problem/binomial_coefficient)
[2015 ICL, Finals, Div. 1　J. Ceizenpok’s formula (nCk mod m の求め方)](https://ferin-tech.hatenablog.com/entry/2018/01/17/010829)
[nCr mod mの求め方 - uwicoder](https://w.atwiki.jp/uwicoder/pages/2118.html)
lucasの定理で素因数ごとに計算して中国剰余定理で戻す。合成数modの問題は素冪の問題に帰着させることが多い気がする。

### [Stirling Number of the First Kind](https://judge.yosupo.jp/problem/stirling_number_of_the_first_kind)
[FFT (NTT) 関連 - memo](https://min-25.hatenablog.com/entry/2015/04/07/160154)

### [Stirling Number of the Second Kind](https://judge.yosupo.jp/problem/stirling_number_of_the_second_kind)
同上

### [Bernoulli Number](https://judge.yosupo.jp/problem/bernoulli_number)
Inv of Formal Power Seriesに貼ったやつ+
[ベルヌーイ数 - Wikipedia - ウィキペディア](https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E6%95%B0)

### [Partition Function](https://judge.yosupo.jp/problem/partition_function)
Inv of Formal Power Seriesに貼ったやつ+
[分割数 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%88%86%E5%89%B2%E6%95%B0#%E5%88%86%E5%89%B2%E6%95%B0%E3%81%AE%E6%AF%8D%E5%87%BD%E6%95%B0)
[オイラーの五角数定理 - Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E4%BA%94%E8%A7%92%E6%95%B0%E5%AE%9A%E7%90%86)

### [Montmort Number](https://judge.yosupo.jp/problem/montmort_number_mod)
[完全順列 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97)
漸化式で簡単に解けます

### [Sum of Totient Function](https://judge.yosupo.jp/problem/sum_of_totient_function)
[トーティエント関数の和$\sum_{i=1}^N\phi(i)$を$O(N^{2/3}(loglogN)^(1/3))で求める](https://yukicoder.me/wiki/sum_totient)

トーティエント関数は乗法的関数なので、Dirichlet級数に関するアルゴリズムと捉えることもできます
[Dirichlet 積と、数論関数の累積和 - maspyのHP](https://maspypy.com/dirichlet-%E7%A9%8D%E3%81%A8%E3%80%81%E6%95%B0%E8%AB%96%E9%96%A2%E6%95%B0%E3%81%AE%E7%B4%AF%E7%A9%8D%E5%92%8C)

### [\sum_{i=0}^{n-1}r^ii^d](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial)
[Polynomial Sum - memo](https://min-25.hatenablog.com/entry/2015/04/24/031413)
[AtCoder ARC #033 : D - 見たことのない多項式　- kmjp's blog](http://kmjp.hatenablog.jp/entry/2015/02/01/1000)
[TKO919さんの提出(コメントに解法がある)](https://judge.yosupo.jp/submission/5568)
(恐らく因数定理と言ってるのはヘビサイドのcover-up method？)

### [\sum_{i=0}^{\infty}r^ii^d](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial_limit)
[無限和を計算するyosupo judgeの問題 - kyopro_friends’ diary](https://kyopro-friends.hatenablog.com/entry/2020/03/11/073122)
[Eulerian number - Wikipedia](https://en.m.wikipedia.org/wiki/Eulerian_number)(TKO919さんありがとうございます！！)
[FFT (NTT) 関連 - memo](https://min-25.hatenablog.com/entry/2015/04/07/160154)

### [Find Linear Recurrence](https://judge.yosupo.jp/problem/find_linear_recurrence)
[Berlekamp–Massey algorithm - メモ](http://sugarknri.hatenablog.com/entry/2017/11/18/234217)
[多項式を使うテクニックたち(yukicoder)](https://yukicoder.me/wiki/polynomial_techniques)

### [Kth term of Linearly Recurrent Sequence](https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence)
[Ryuhei Moriさんのblog](http://q.c.titech.ac.jp/docs/progs/polynomial_division.html)
[線形漸化的数列のN項目の計算 - Qiita](https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a)
Bostan–Mori のアルゴリズムと呼ばれるアルゴリズムがFiduccia のアルゴリズムよりも高速かつ軽実装であることからよく使用される。Find Linear Recurrenceと合わせて出題される事も多い。

### [Sum of Floor of Linear](https://judge.yosupo.jp/problem/sum_of_floor_of_linear)
[格子点の数え上げの高速化 - memo](https://min-25.hatenablog.com/entry/2018/05/03/145505)
[Scary Sum - memo](https://min-25.hatenablog.com/entry/2018/04/27/225535)
[sum of floor of linear の解説するよ - えびちゃんの日記](https://rsk0315.hatenablog.com/entry/2020/12/13/231307)
きちんと考察すれば自力でもいけます
台形内の格子点を求めればいいですが、(x,y)座標の反転を繰り返す事で互除法っぽく三角形領域を切り取っていきます

### [Sqrt Mod](https://judge.yosupo.jp/problem/sqrt_mod)
[Tonelli–Shanks algorithm - メモ](http://sugarknri.hatenablog.com/entry/2018/02/16/115740)
[整数論テクニック集 - kirika_compのブログ](http://kirika-comp.hatenablog.com/entry/2018/03/12/210446)

### [Kth Root(Mod)](https://judge.yosupo.jp/problem/kth_root_mod)
[No.981 一般冪乗根 解説 -yukicoder](https://yukicoder.me/problems/no/981/editorial)
yukicoderに似たような問題がある

### [Kth Root(Integer)](https://judge.yosupo.jp/problem/kth_root_integer)
[二分探索アルゴリズムを一般化 〜めぐる式二分探索法のススメ 〜](https://qiita.com/drken/items/97e37dd6143e33a64c8c)
[C++ (gcc) で 128 ビット整数を使う - 宇宙ツイッタラーXの憂鬱](https://kenkoooo.hatenablog.com/entry/2016/11/30/163533)

### [Discrete Logarithm](https://judge.yosupo.jp/problem/discrete_logarithm_mod)
[「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a)
xとMが互いに素で無い場合が難しいが、$x$と$M/g$が互いに素になるような値$g$を取ってきて
$x^n \equiv y (mod\ g)$かつ$x^n \equiv y (mod\ M)$となるような値を走査する感じでACは出来た

### [Tetration Mod](https://judge.yosupo.jp/problem/tetration_mod)
[Tetration - My Algorithm : kopricky アルゴリズムライブラリ](https://kopricky.github.io/code/Computation_Advanced/tetration.html)
[フェルマーの小定理 - Wikipedia/カーマイケルの定理](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86#%E3%82%AB%E3%83%BC%E3%83%9E%E3%82%A4%E3%82%B1%E3%83%AB%E3%81%AE%E5%AE%9A%E7%90%86)
$2^k \geq m$の時$a^{n+k} \mod m$は$φ(m)$の約数周期を持つ事を念頭において解きます
~~koprickyさんのコードは$a=0$のコーナーが抜けてるので注意しましょう(この場合$(b+1)\%2\%m$を出力)~~ 修正していただきました

### [Nim Product (\mathbb{F}_{2^{64}})](https://judge.yosupo.jp/problem/nim_product_64)
競プロフレンズさんによるわかりやすい解説がいつの間にか生まれてた！！
通し直そうかな
[Nim product - kyopro_friends’ diary](https://kyopro-friends.hatenablog.com/entry/2020/04/07/195850)
[Nimber - Wikipedia](https://en.wikipedia.org/wiki/Nimber)
[Nim Multiplication - Code Golf Stack Exchange](https://codegolf.stackexchange.com/questions/164318/nim-multiplication)

### [#_p Subset Sum](https://judge.yosupo.jp/problem/sharp_p_subset_sum)
部分和問題は$[x^M]\prod_{i=0}^N(1+x^{A_i})$で表せるので
$[x^M]\exp(\sum_{i=0}^Nlog(1+x^{A_i}))$を計算するだけ
[A Simple Near-Linear Pseudopolynomial Time
Randomized Algorithm for Subset Sum](https://arxiv.org/pdf/1807.11597.pdf)

### [2 Sat](https://judge.yosupo.jp/problem/two_sat)
[2SAT(充足可能性問題)の解き方 - SlideShare](https://www.slideshare.net/yoshiokatsuneo/2sat-72370606)
[2-SAT のアルゴリズムの証明 - noshi91のメモ](http://noshi91.hatenablog.com/entry/2019/10/03/184812)

# Convolution

### [Convolution](https://judge.yosupo.jp/problem/convolution_mod)
[FFT（高速フーリエ変換）を完全に理解する話](https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79)
[数論変換 (Number Theoretic Transform; NTT) - るまライブラリ](https://lumakernel.github.io/ecasdqina/math/FFT/NTT)
実用にはNTTの方がおすすめですがFFTから作るのがいいと思います

[Convolution - Atcoder Library](https://atcoder.github.io/ac-library/production/document_ja/convolution.html)
Atcoder社が用意しているライブラリが存在する

### [Convolution (mod 1,000,000,007)](https://judge.yosupo.jp/problem/convolution_mod_1000000007)
[[数学・numpy] 高速フーリエ変換(FFT)による畳み込み - maspyのHP](https://maspypy.com/%E6%95%B0%E5%AD%A6%E3%83%BBnumpy-%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9Bfft%E3%81%AB%E3%82%88%E3%82%8B%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF)
[任意modでの畳み込み演算をO(n log(n))で - math314のブログ](https://math314.hateblo.jp/entry/2015/05/07/014908)

### [Convolution(mod 2^64)](https://judge.yosupo.jp/problem/convolution_mod_2_64)
[Convolution (mod 2^64)](Fast convolution for 64-bit integers - Codeforces)

### [Convolution (Large)](https://judge.yosupo.jp/problem/convolution_mod_large)
速度計測のために用意されたようである。

### [Subset Convolution](https://judge.yosupo.jp/problem/subset_convolution)
[Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets möbius: fast subset convolution. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC ’07). Association for Computing Machinery, New York, NY, USA, 67–74. / arxiv:](https://arxiv.org/abs/cs/0611101)
[指数時間アルゴリズム入門 - SlideShare](https://www.slideshare.net/wata_orz/ss-12131479)
s and t=0∧s or t=kを
s or t=k∧sとtの立ってるビット数の和がkの立ってるビット数に等しい
に言い換えると、多項式をor畳み込みすればOKとわかる

### [Bitwise And Convolution](https://judge.yosupo.jp/problem/bitwise_and_convolution)
[ゼータ変換・メビウス変換を理解する](https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5)

### [Bitwise Xor Convolution](https://judge.yosupo.jp/problem/bitwise_xor_convolution)
[色々な畳み込み - kazuma8128’s blog](https://kazuma8128.hatenablog.com/entry/2018/05/31/144519)

### [Multivariate Convolution](https://judge.yosupo.jp/problem/multivariate_convolution)
[Multivariate Multiplication - Nyaan's Library](https://nyaannyaan.github.io/library/ntt/multivariate-multiplication.hpp)

### [Convolution on the multiplicative monoid of Z / 2^N Z](https://judge.yosupo.jp/problem/mul_mod2n_convolution)
[[問題案] Convolution on the multiplicative monoid of Z/NZ - Github](https://github.com/yosupo06/library-checker-problems/issues/747)

# Polynomial

### [Inv of Formal Power Series](https://judge.yosupo.jp/problem/inv_of_formal_power_series)
[【競技プログラミング】形式的冪級数の応用テクニック(前編) - Qiita](https://qiita.com/hotman78/items/f0e6d2265badd84d429a)
[[多項式・形式的べき級数] 高速に計算できるものたち - maspyのHP](https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0-%E9%AB%98%E9%80%9F%E3%81%AB%E8%A8%88%E7%AE%97%E3%81%A7%E3%81%8D%E3%82%8B%E3%82%82%E3%81%AE)
[形式的べき級数 - メモ](http://sugarknri.hatenablog.com/entry/2019/10/08/001359)
[Operations on Formal Power Series - Codeforces](https://codeforces.com/blog/entry/56422)

### [Exp of Formal Power Series](https://judge.yosupo.jp/problem/exp_of_formal_power_series)
同上

### [Log of Formal Power Series](https://judge.yosupo.jp/problem/log_of_formal_power_series)
同上

### [Pow of Formal Power Series](https://judge.yosupo.jp/problem/pow_of_formal_power_series)
同上、log取ってM倍してexp取るだけだが初項に1が来るように調整が必要だったはず

### [Sqrt of Formal Power Series](https://judge.yosupo.jp/problem/sqrt_of_formal_power_series)
同上

### [Multipoint Evaluation](https://judge.yosupo.jp/problem/multipoint_evaluation)
[Multipoint evaluationの高速実装](https://www.sci.kanagawa-u.ac.jp/info/matsuo/pub/pdf/IKM09.pdf)
[因数定理 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%9B%A0%E6%95%B0%E5%AE%9A%E7%90%86)
[データ構造をマージする一般的なテク - るまぶろぐ-tomorinao](https://tomorinao.blogspot.com/2018/10/blog-post_39.html)

### [Polynomial Interpolation](https://judge.yosupo.jp/problem/polynomial_interpolation)
[非再帰で補間多項式を求めるよ - えびちゃんの日記](https://rsk0315.hatenablog.com/entry/2020/04/05/203210)

### [Polynomial Taylor Shift](https://judge.yosupo.jp/problem/polynomial_taylor_shift)
[多項式を使うテクニックたち -yukicoder](https://yukicoder.me/wiki/polynomial_techniques)

### [Shift of Sampling Points of Polynomial](https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial)
[[問題案] Shift of Sampling Points - Github](https://github.com/yosupo06/library-checker-problems/issues/680)
[階乗冪 - Wikipedia](https://ja.wikipedia.org/wiki/%E9%9A%8E%E4%B9%97%E5%86%AA)
標準基底を用いた多項式に戻してから計算すると $\mathcal{O}(N\log^2 N)$ かかってしまうが、下降冪の形に直すことでも二項定理の様な物が成り立つことから Taylor Shift が可能であり、$\mathcal{O}(N\log N)$。

### [Division of Polynomials](https://judge.yosupo.jp/problem/division_of_polynomials)
[Inv of Formal Power Series](#inv-of-formal-power-series)に貼ったやつ。
形式的ローラン級数 $F_p((x^{-1}))$ の文脈でアルゴリズムを整理する事も出来る。

### [Inv of Polynomials](https://judge.yosupo.jp/problem/inv_of_polynomials)
[多項式GCD - Nyaan's Library](https://nyaannyaan.github.io/library/fps/polynomial-gcd.hpp.html)
half GCD という手法を利用することで $\mathcal{O}(N \log^2 N)$ で多項式のGCDが出来、これは拡張ユークリッドの互助法と同様の手法でInv of Polynomialsが解ける形に拡張が可能である。

# Matrix
### [Matrix Product](https://judge.yosupo.jp/problem/matrix_product)
[行列の積の定義とその理由 - 高校数学の美しい物語](https://manabitimes.jp/math/1023)
未確認だが恐らく愚直に計算しても間に合う。
[シュトラッセンのアルゴリズム - Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A5%E3%83%88%E3%83%A9%E3%83%83%E3%82%BB%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
シュトラッセンのアルゴリズムよりも計算量のオーダーが小さいアルゴリズムが存在するが、実用的には低速

### [Determinant of Matrix](https://judge.yosupo.jp/problem/matrix_det)
[行列式の計算 - Tech Tips](http://techtipshoge.blogspot.com/2011/08/blog-post_23.html)
[Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/entry/2019/03/20/202800)
[行列式の計算（4） - inamori's diary](https://inamori.hateblo.jp/entry/20080914/p1)

### [Determinant of Sparse Matrix](https://judge.yosupo.jp/problem/sparse_matrix_det)
LU分解+sparse性を利用してbitset高速化するゴリ押しでも解けることには解けます...(非零要素をx,y座標それぞれについてbitsetで持っておく)
[LU分解 - [物理のかぎしっぽ]](http://hooktail.org/computer/index.php?LU%CA%AC%B2%F2#:~:text=%E6%AC%A1%E3%81%AE%E3%82%88%E3%81%86%E3%81%AB%E3%81%82%E3%82%8B,%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%82%92%E8%80%83%E3%81%88%E3%81%BE%E3%81%99%EF%BC%8E)
[bitset Find_first and Find_next -codeforces](https://codeforces.com/blog/entry/43718)

### [System of Linear Equations](https://judge.yosupo.jp/problem/system_of_linear_equations)
<blockquote class="twitter-tweet"><p lang="ja" dir="ltr"><a href="https://twitter.com/hotmanww?ref_src=twsrc%5Etfw">@hotmanww</a> <br>Qiitaのyosupo judge全完記事、まだ募集しているかはわからないですが<br>・Determinant of sparse matrix はこれです<a href="https://t.co/BlXbdFCl08">https://t.co/BlXbdFCl08</a><br>・System of linear equations はアルゴリズムという程のものではないですが、Gaussの掃き出しで階段行列に変形して解くものです</p>&mdash; moni (@onakasuita_py) <a href="https://twitter.com/onakasuita_py/status/1326473507828494336?ref_src=twsrc%5Etfw">November 11, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

[Black box linear algebra - yukicoder](https://yukicoder.me/wiki/black_box_linear_algebra)
これが想定解みたいです(moriさんありがとうございます！！)

### [Inverse Matrix](https://judge.yosupo.jp/problem/inverse_matrix)
[Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/entry/2019/03/20/202800)

### [Characteristic Polynomial](https://judge.yosupo.jp/problem/characteristic_polynomial)
[ハウスホルダー行列とその性質 - 具体例で学ぶ数学](https://mathwords.net/householder)
[QR法 - いろはの物置き場](https://168iroha.net/blog/topic/?id=201911251209&sorting=post_date)
ハウスホルダー変換を用いてヘッセンベルグ行列への相似変換を行い、これを使用して求める。
~~[System of Linear Equations](#system-of-linear-equations) の項に前述したBlack box linear algebraを用いても確率的に解けそうである。~~ これでは最小多項式しか求められず、嘘の可能性が高いです。申し訳ありません。(10/08 09:01 追記)

### [Hafnian of Matrix](https://judge.yosupo.jp/problem/hafnian_of_matrix)
定義は簡単だけど求めるのは大変...偶奇だけなら簡単です(行列式と一致します)
[行列のパフィアン，パーマネント，ハフニアン -　高校数学の美しい物語](https://mathtrain.jp/pfaffian)
[Björklund, A. (2012, January). Counting perfect matchings as fast as Ryser. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (pp. 914-921). Society for Industrial and Applied Mathematics.](https://dl.acm.org/doi/pdf/10.5555/2095116.2095189)
ハフニアン(無向グラフの完全マッチングの個数)

# String
### [Z Algorithm](https://judge.yosupo.jp/problem/zalgorithm)
[【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く](https://qiita.com/Pro_ktmr/items/16904c9570aa0953bf05)

### [Enumerate Palindromes](https://judge.yosupo.jp/problem/enumerate_palindromes)
[文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ](https://snuke.hatenablog.com/entry/2014/12/02/235837)


### [Suffix Array](https://judge.yosupo.jp/problem/suffixarray)
[Suffix ArrayのO(NlogN)構築（とおまけでSA-IS） - 足跡-sokuseki-](http://wk1080id.hatenablog.com/entry/2018/12/25/005926)

### [Number of Substrings](https://judge.yosupo.jp/problem/number_of_substrings)
[I - Number of Substrings - Atcoder](https://atcoder.jp/contests/practice2/tasks/practice2_i)
Suffix Array+LCPで解けます
[Suffix Automatonの作り方と使い方 - uwicoder](https://w.atwiki.jp/uwicoder/pages/2842.html)
Suffix Automatonでも解けます

### [Run Enumerate](https://judge.yosupo.jp/problem/runenumerate)
[Runの列挙 (Main-Lorentz algorithm) - 迷いませんか？](http://pazzle1230.hatenablog.com/entry/2019/11/27/234632)
これわかりやすいです
Suffix Automatonでも解けるらしいです

# Geometry
### [Sort Points by Argument](https://judge.yosupo.jp/problem/sort_points_by_argument)
[C++で点を偏角ソートをしたい(反時計にソートしたい)【軽実装編】](https://qiita.com/ganariya/items/adef1a7f89ae88b804da)
上下に分けて外積(というより傾きの式の式変形)やる方が良いと思います

### [Convex Layers](https://judge.yosupo.jp/problem/convex_layers)
[Dynamic convex hull implementation - Codeforces](https://codeforces.com/blog/entry/75929)
decremental convex hull を処理できるデータ構造を使用して、「convex hullを求める」、「convex hullに含まれる頂点を削除する」を交互に繰り返します。