整数論

[customaddone]

逆元 １　フェルマーの小定理を使う ２　拡張ユークリッド互除法を使う ことで求められる ２は1/x mod y = (y + form_ext(x, y, 1)[1][1]) % yで求められる https://github.com/customaddone/beginPython/blob/master/cgi-bin/library/math/ext_Euclid_%26_CRT.py

これは素数pについて定まる環準同型Z→Z/pZが環準同型Z(p)→Z/pZに拡張できる(Z(p)は分子が任意、分母がpの倍数でないような分数全体)といえる、つまり、整数→整数 mod pとしたのと同様に分数(分子はpと互いに素)→整数 mod pにできるということ

[customaddone]

二分累乗法 モノイドは二分累乗できる（逆元はなくていい） a^0, a^1, a^2...をそのまま持つと嬉しくなさそうだけど、mod pで持つと値が小さくなり嬉しい 123123123... のmod pを求める問題 [[0, 1]]に[[10 ** r, 0], [a, 1]](r = len(a))をたくさん掛ける　これは行列累乗で求められる https://atcoder.jp/contests/arc020/submissions/20915229 C - A mod B Problem

[customaddone]

素数の密度 正の整数p, yが与えられる。2以上p以下のどのような整数iについてもz = ki(k >= 2)と表されないような、y以下の最大の整数zを求めよ 2 <= p <= y <= 10 ** 9 2以上p以下のどの整数の倍数にもならないy以下の最大の整数zを探す まずzを素数にすると確実　y以下の最大の素数 <= opt <= yが候補 y付近の素数の密度は1/logy程度なのでlogy個探索すれば見つかる

[customaddone]

平方剰余 a = x^2(mod p)なるxが存在する場合、aをpにおける平方剰余という pが奇素数の時, 1~p-1の中の平方剰余と平方非剰余の割合は1:1 またa^(p-1)//2 (pの半分分累乗する)は平方剰余の時1で平方非剰余の時-1

p = 13の時　平方剰余は1 = 1^2, 4 = 2^2, 10 = 6^2など また、適当な平方非剰余zを取ると、0以外の平方剰余にzを掛けたものは全て平方非剰余

あるxについてa = x^2 (mod p)が成り立つaが与えられる　このときxを求めよ 奇素数pの候補は2, 4m + 1, 4m + 3 2の時はx = aとすればいい 4m+3の時はx = a^((p+1)//4)とする x^2 = a^((p+1)//2) = a^((p-1)//2)*a で a = y^2となるyが存在するのでa^((p-1)//2) = y^(p-1) = 1(フェルマーの小定理)

[customaddone]

群論 群: 単位元、結合法則、逆元を持つ 対称群: n要素の置換の全体 巡回群: ある要素gをが存在しており、gの演算のみでGの任意の要素を表せる

Z/mZの乗法群(Z/mZ)*: mと互いに素な元の集合 (Z/10Z)p = {1, 3, 7, 9}

[customaddone]

二分探索 多少グラフが揺れてても値を求められる場合もある 【ABC026 D - 高橋君ボール1号】 【ABC165 D - Floor Function】 二分探索＋累積和で数え上げ 【ABC077 C - Snuke Festival】 【ARC43 B - 難易度】

[customaddone]

dfs, bfs rangeの部分を適当にいじって回せる 【パナソニックプログラミングコンテスト2020 D - String Equivalence】

[customaddone]

dp

メモdp 要素aの最大値が小さいとdp回せる 【ABC004 D - マーブル】（適当な範囲について）置く、置かない（ボールの色の区別をしない）

桁dpで 数字内に1がN個あるもの【ABC154 E - Almost Everywhere Zero】【ABC029 D - 1】 数字内に4, 9がつく数字の通りの数【ABC007 D - 禁止された数字】（上の簡易版) 二進数で次の桁が1なら通りが2倍になる【ABC129 E - Sum Equals Xor】 がわかる

bit dp 【CODE FESTIVAL 2017 Final C - Time Gap】 なんとかしてN（最大50）の数を減らす 条件だとN <= 50になってるが実際にはもっと少ないのではないか

[customaddone]

グラフ　通りの数 ①グローバル変数ansを設定し、足し合わせ、掛け合わせする方法 【ABC133 E - Virus Tree 2】グラフを塗るのに必要な色のリストを事前に持ってき、後で追加する 【ABC146 D - Coloring Edges on Tree】

②各頂点から順に下ろしていく方法 【ABC021 C - 正直者の高橋くん】 【ABC138 D - Ki】

③各頂点の属性（rootからの距離、隣接エッジ数など）で分けてそれぞれのグループについて答えを求める 【ABC044 B - 最短路問題】距離iの頂点から線を引くと距離i + 1の頂点になる　i + 1の頂点間に線を引いても最短距離は変わらない

[customaddone]

グラフ　最短距離 ワーシャルフロイドは全点対最短経路問題 各地点から各地点まで最短経路でいけるエッジとしてどれを残すかを求められる 【ABC051 D - Candidates of No Shortest Paths】 【ABC074 D - Restoring Road Network】

ダイクストラは単一始点最短経路問題を解くのに使う 有向グラフは逆向きにすることも考える 【ABC035 D - トレジャーハント】

ベルマンフォードは負の距離があるときに使える 各エッジに対してN - 1ループすると答えが出る 【ABC061 D - Score Attack】負経路検出 【ABC137 E E - Coins Respawn】無限ループに注意 N回目に訪れた時の最短経路も保持できる 【ABC132 E - Hopscotch Addict】

木は経路復元すれば各点からrootまでの経路、距離を調べられる 【ABC067 D - Fennec VS. Snuke】 【ARC030 B - ツリーグラフ】 更にダイクストラを併用することで（閉路ありグラフの）ある点からrootまでの経路、最短距離を調べられる 【ARC011 C - ダブレット】

[customaddone]

グラフ　maze 最短距離を求める場合は幅優先探索 【ABC007 C - 幅優先探索】 【ABC151 D - Maze Master】

ぐねぐね進む場合は深さ優先探索 【ABC037 D - 経路】

ダイクストラを用いて最短経路を求めることもある mazeはグリッドグラフ 【ABC020 C - 壁抜け】

[customaddone]

UnionFInd aとbがグループ内にいるときのみ判定する 【ABC002 D - 派閥】 【ABC157 D - Friend Suggestions】　集合（グループ/グループ以外　友達/ブロック/それ以外）を分ける 繋いでいきつつqueryに答える 【ABC120 D - Decayed Bridges】 unionの解消はできないが、後ろから処理していくことで擬似的には可能 【ARC056 B - 駐車場】後ろから処理する　スタート地点と頂点が同じ集合か調べる→その頂点と既に調べた頂点とのエッジを繋ぐ queryは[前のもの, 後ろのもの]というふうに並び替える

[customaddone]

累積和、しゃくとり

[customaddone]

nim まず全通りについて試してみる 【ABC027 C - 倍々ゲーム】 【CADDi2018 D - Harlequin】山が複数あるnim 【ABC059 D - Alice&Brown】二次元表で全通りについて書いてみる サイズが小さければ全探索もいける（勝ちになるルートに一つでも進めれば勝ち) 【ARC038 B - マス目と駒】 最終形をイメージする 【ABC048 D - An Ordinary Game】 ゲーム木 【ARC038 B - マス目と駒】ゴールから順に探索する 【ABC025 C - 双子と○×ゲーム】それ以降の手についてすべて探索する

[customaddone]

整数問 要素をそれぞれ分解してみることはできないか 【ABC151 E - Max-Min Sums】 【ABC172 D - Sum of Divisors】f(n) = 4ならその４について○○の時の+=1, ××の時の+= 1というふうに考える 【SoundHound Inc C - Ordinary Beauty】配列mの長さを1伸ばした時に+=n増える、また1伸ばした時に...と考える

「1 ~ Kまでの○○の合計」問は総和の公式を使えないか検討する 例:Σk = N(N + 1) // 2, Σk 2 = N(N + 1)(N + 2) // 6, Σk 3 = (N(N + 1) // 2) 2, nC0 + nC1 + ... = 2 N 【ABC172 D - Sum of Divisors】 【ABC156 D - Bouquet】 各要素をmodでグルーピングする（連続性があるため対称性がある） 【ABC108 C - Triangular Relationship】 【ABC096 D - Five, Five Everywhere】

もしくは１変数を固定してそれぞれO(1)で値を求めてO(N)で返す 【ABC163 D - Sum of Large Numbers】

値が大きくなる場合は素因数の集合で持つ 【ABC152 E - Flatten】

素数はリスト作成してi 2, i 3...するか素数判定するか 【ABC170 D - Not Divisible】

[customaddone]

文字列

前から読み込む 【ABC149 D - Prediction and Restriction】 文字列をリストに直して操作する 【ABC158 D - String Formation】 アルゴリズム 【ABC141 E - Who Says a Pun?】z-algorithm

[customaddone]

Xor

二進数に直した数字について、それぞれの桁で分けて考える それぞれの要素は2 ** iの桁が1か2かで場合分けできる 【ABC147 D - Xor Sum 4】 a ~ bまでのフラグを全て保持する 【ABC121 D - XOR World】 桁dpも使える 【ABC129 E - Sum Equals Xor】 【ABC117 D - XXOR】 論理積問題 【第5回 ドワンゴからの挑戦状 予選　B - Sum AND Subarrays】クリアするたびにフラグを増やして条件を厳しくする

[customaddone]

最大流 最大マッチングを求められる 【ABC091 C - 2D Plane 2N Points】 【CODE FESTIVAL 2014 予選B C - 錬金術士】 エッジの長さを1にして最小カットを求められる 【ABC010 D - 浮気予防】 最小費用流 【ABC004 D - マーブル】

[customaddone]

確率、丸め誤差

最後にまとめて整数 / 整数する（途中で割り算をするとfloat型に切り替わって大きい数字だと保持できない） 【ABC011 D - 大ジャンプ】 decimalを使うか整数だけで扱えるようにする 【パナソニックプログラミングコンテスト2020 C - Sqrt Inequality】

[customaddone]

ゲーム木 【ARC038 B - マス目と駒】ゴールから順に探索する 【ABC025 C - 双子と○×ゲーム】それ以降の手についてすべて探索する