関連記事
mod
- オイラーの定理
- 逆元計算（フェルマーの小定理）と組合せ計算
- 解説 uwiさんのここに組合せの全てがある
- フェルマーの小定理を使う問題
- 0で除算することは出来ないので注意 これ
- yukicoder No.117 組み合わせの数 (二項定理系ライブラリ最強Verify問題)
- AGC025 RGB Coloring 解説
- yukicoder No.573 a^2i = ai 解説
- No.389 ロジックパズルの組み合わせ
- ECR33 Counting Arrays 解説
- 中国人剰余定理
- ABC110 Factorization 解説 （nHk）
- 離散対数問題
- 素数pと定数gと整数yが与えられた時、g^x ≡ y (mod p)を満たすxを求める問題 アルゴリズムまとめ tubo28さんの実装例
- yukicoder No.551 夏休みの思い出（２） 解説1 解説2 解説3 解説4
- yukicoder No.261 ぐるぐるぐるぐる！あみだくじ！
- AtCoder 乱数調整 解説1 解説2
- AtCoder あまり 解説
- yukicoder No.251 大きな桁の復習問題(1)
- CSA Fibonacci Mod Baby-Step Giant-Stepで解く
- 平方剰余
- 乱択アルゴリズム
- Tonelli–Shanks algorithm
- Cipolla's algorithm
- 離散対数問題の一部と考えると、Baby-step giant-stepアルゴリズムでも解ける
- yukicoder No.551 夏休みの思い出（２） 解説1 解説2 解説3 解説4
- CF395 Timofey and remoduling 解説
- ウィルソンの定理
- (M-1)! ≡ -1 (mod M)という定理がウィルソンの定理 解説
- ルーカスの定理【発展的話題】 CRT(中国人剰余定理)とルーカスの定理を使うと解ける二項定理
- 分かりやすいまとめ
- （C(n,m)でn,m≦10^5であれば、違うもっと早い方法があるみたい） この問題のどっかの解説
- 問題
- modには大体周期性がある（ほんとか？）
- N! mod MがO(sqrt(M)logM)で計算できるらしい 引用元
数学的知識
- アルゴリズム
- 繰り返し二乗法による累乗高速化
- 整数問題
- 素数判定
- 素因数分解（Pollard's rho algorithm）
- 大体O(sqrt(N))の手法を使えばいい
- ミラーラビンとロー法について
- POJ Prime Test 解法
- UVA Factorizing Larget Integers 解法
- CF Divisions
- HE Count of paths
- AC Product and GCD
- AOJ 約数ゲーム / Divisor Game 解説
- [https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_f:title=[いろはちゃんコンテスト Day1 Head of The Dragon] 解説
- 約数列挙 O(sqrt(N))
- 高度合成数
- それ未満のどの自然数よりも約数の個数が大きい自然数
- これを使う問題はあまり見かけないが、約数の個数があまり多くないから全探索できる理論の担保として見かけたりする
- 一覧がOEISにある [A002182 - OEIS](https://oeis.org/A002182) [raw](http://oeis.org/A002182/b002182.txt)
- 一応調べた
- 10^6以下最大：720720で240個
- 10^9以下最大：735134400で1344個
- 10^12以下最大：963761198400で6720個
- これ以上は約数列挙が難しい
- 素数定理
- http://www.isc.meiji.ac.jp/~random/lecture/2016-calc1/ishii.html
- x以下の素数の個数は大体x/logx個
- GCD,LCM
- ユークリッドの互除法
- GCDの最悪計算回数はフィボナッチ数列になる
- ある数aを素因数がある数bの素因数に全て含まれるかをgcdを使って判定することができる 問題 言及
- AOJ 電線
- yukicoder No.736 約比 解説
- 平方数
- 互いに素な個数
- [1,n]でnと互いに素な個数はトーティエント関数
- [1,n]でgと互いに素な個数はn≦10^6なら包除原理で解ける これ
- 拡張ユークリッドの互除法
- ax+by=cの整数解(x,y)を求めるアルゴリズム 参考1 参考2 参考3
- https://yukicoder.me/wiki/拡張ユークリッド互除法
- SRM735 Div1 Med 解説
- 自然数をいくつかの自然数の和で表現する系
- ゴールドバッハ予想
- 他一覧
- 記数法
- 位取り記数法、N進数
- 日常的に使ってるのは10進数だし、パソコン内部では2進数だし、プログラマなら16進数もなじみがあるだろう
- N進数の考え方が分かっていると解きやすい問題も多くある
- 例外的な考え方もあるが、10進数をN進数に変換した後の形は一意に定まる
- 平衡N進法(Nは3以上の奇数)
- 例）平衡3進法
- 通常の3進法では、a_N*3^N+a_{N-1}*3^{N-1}+...+a_0*3^0で、a_iは0,1,2である
- 平衡3進法では、a_N*3^N+a_{N-1}*3^{N-1}+...+a_0*3^0で、a_iは-1,0,1である
- 変換方法：[広義の記数法 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%BA%83%E7%BE%A9%E3%81%AE%E8%A8%98%E6%95%B0%E6%B3%95#%E5%8D%81%E9%80%B2%E6%B3%95%E3%81%8B%E3%82%89%E3%81%AE%E5%A4%89%E6%8F%9B%EF%BC%88%E6%95%B4%E6%95%B0%E9%83%A8%E5%88%86%EF%BC%89)
- （例外的な考え方もあるかは知らないけど、）10進数を平衡N進数に変換した後の形は一意に定まる
- 問題
- [平衡三進法 カテゴリーの記事一覧 - けんちょんの競プロ精進記録](https://drken1215.hatenablog.com/archive/category/%E5%B9%B3%E8%A1%A1%E4%B8%89%E9%80%B2%E6%B3%95)
- [No.1106 🦉 何事もバランスが大事 - yukicoder](https://yukicoder.me/problems/no/1106)
- 位取り記数法、N進数
- 加法的関数・乗法的関数
- 一覧
- 乗法的関数
- http://codeforces.com/contest/757/problem/E
- http://pekempey.hatenablog.com/entry/2017/01/13/065659#E-Bash-Plays-with-Functions
- https://www.hackerrank.com/contests/infinitum18/challenges/divisor-exploration-3
- http://codeforces.com/blog/entry/46642
- https://www.hackerrank.com/contests/w3/challenges/gcd-product
- メビウス関数
- トーティエント関数
- phi(n) := x=[1,n]でgcd(x,n)=1となる数（n以下でnと互いに素な数の個数）
- ax = 1 (mod m) かつ gcd(a,m) = 1 互いに素の時のxを求められる。(拡張ユークリッドの互除法でも求められる)
- なぜか出て来る : https://www.hackerrank.com/contests/101hack50/challenges/cutting-the-string/editorial
- yukicoder No.644 G L C C D M
- nの素因数をp1,p2,...,pkとすると、phi(n) = n * (1-1/p1)*(1-1/p2)*...*(1-1/pk) CF538 Please, another Queries on Array? 解説
- 数字根
- ある数Nの桁和（各桁の数字の総和を取ったもの）を1桁になるまで行ったときの最終的な値を数字根という
- ある数Nを9で割った余りと数字根が一致するという性質がある（ただしNを9で割った余りが0の時は数字根は9か0であり、N=0であるときのみ数字根0となる）
- 余りが0の部分が問題でコーナーケースとなることが多い
- この性質を使った検算方法として、九去法というのがある
- 問題
- 幾何
- 凸法
- ピックの定理: 格子点（座標がどちらも整数の頂点）の場合の多角形の面積を求める、格子点問題で使える、ほとんど解いてなくて違うの混ざってるかも
- ARC018 格子点と整数 （←ピックの定理は使わないけど、格子点問題として載せとく）
- HR Integral Points （たぶんピックの定理やるだけ、入門問題）
- CC Ant Colony 解説
- AC 三角形と格子点
- AC Triangles
- CF313 Randomizer 解説
- CC Save The Trees 解説
- CC Needles and Pins 解説
- 三角関数の漸化式
- 組合せ問題
- カタラン数
- 正しい括弧列はdyck 列やcorrect bracket sequencesとも言うが、その組み合わせ数がカタラン数
- （の数ー）の数が負にならず、深さ上限もある場合に上手くひっくり返して数え上げるらしい 参考
- 問題と所感
- AOJ １０歳の動的計画 解説（最も初歩的な適用例な気がする）
- yukicoder No.660 家を通り過ぎないランダムウォーク問題 解説（これも初学者向けに悪くない）
- AOJ Steps 解説（包除原理とかも入ってくる。下限だけでなく上限も制約付き）
- AGC021 Ball Eat Chameleons 解説（カタラン数っぽいが、境界線が少し違う。考察が重い）
- CF449 Nephren Runs a Cinema（典型的なカタラン数適用問題らしいが、aCbmod任意がキツイ）
- HR Brackets Restoring 解説
- 写像12相
- 資料1 資料2 資料3
- これらは上手くDPできる場合が多い
- メモ
- べき乗和の公式
- ベル数
- N個の物を分割する方法の総数 参考
- 「B[n+1]=sum{i=0..n}C(n,k)B[k]」で計算可能
- http://kmjp.hatenablog.jp/entry/2015/08/12/0930
- 第2種スターリング数と関連がある
- σ加法族とベル数の関連性
- CF315 Symmetric and Transitive 解説
- B(n,m) := n個の区別する玉をmグループ以下に分割する組合せ これはO(min(n,m))で計算可能 問題
- 分割数
- 第一種スターリング数
- 別解であるが、第一種スターリング数を用いて解答する
- O(NlogN)で計算できる
- 類題かも
- ポリアの数え上げ定理
- カタラン数
- 線形近似
- 多項式と母関数(全然良くわかってない、全く別のも混じってるかも)
- コドフォでrngさんの形式的冪級数紹介
- ラグランジュ補間
- N+1個の異なる座標がわかっていれば、y=P(x)を復元できる
- xはどのxでも良いが、高速に計算するにはx=0..Nの座標を使う必要がある
- O(NlogMOD)くらいで行ける
- 一般式が多項式で書ける必要がある
- 問題
-
- 多項式を利用して解く
- ARC084 XorShift 解説
- yukicoder No.579 3 x N グリッド上のサイクルのサイズ(hard)
- かなり難しいっぽい。2変数母関数を作る必要があるらしい
- 線形漸化式ってなんだろう
- http://codeforces.com/problemset/problem/168/E?mobile=true
- http://codeforces.com/problemset/problem/493/E
- AC Cyclic GCDs
- 母関数を利用した数え上げ
- Formal Power Series (形式的冪級数) 何もわかってない
- http://beet-aizu.hatenablog.com/entry/2019/09/27/224701
- https://codeforces.com/topic/56727/en1?locale=ru
- https://codeforces.com/contest/438/problem/E?locale=en
- https://codeforces.com/blog/entry/13851
- https://codeforces.com/contest/438/problem/E
- https://codeforces.com/contest/1193/problem/A
- https://wiki.algo.is/Formal%20power%20series
- https://cp-algorithms.com/algebra/polynomial.html
- https://www.codechef.com/problems/RNG
- https://codeforces.com/gym/102129/problem/D
- https://codeforces.com/gym/102129/problem/G
- https://codeforces.com/gym/102129/problem/C
- https://ei1333.github.io/luzhiled/snippets/math/polynominal-mod.html
- https://yukicoder.me/wiki/polynomial_techniques
- 多項式を利用して解く
-
- 冪乗和を高速に求める
- ファウルハーバーの公式というのがあり、ベルヌース数を用いる
- HR Summing the K-N series ファウルハーバーやるだけ問題
- yukicoder No.665 Bernoulli Bernoulli ファウルハーバー
- ECR7 The Sum of the k-th Powers ファウルハーバーじゃ間に合わない？
- HR Highway Construction ファウルハーバー+二項定理による分解
- 冪乗和はファウルハーバーよりより良い方法があるかも
- 以下、その他
- https://erdos.sdslabs.co/problems/7 解説
- https://www.codechef.com/FEB16/problems/WRDSUM 出典
- https://www.codechef.com/problems/SFUNC
- 微分を使って解く
- 未解決
- KEYENCE Programming Contest 2019 F - Paper Cutting（期待値？）
- http://koba-e964.hatenablog.com/entry/2019/01/14/003307
- https://twitter.com/catupper/status/1084461359801151488
- https://twitter.com/evima0/status/1084450651407507460
- https://twitter.com/sigma425/status/1084450874485760002
- https://twitter.com/n_vip/status/1084451819906945024
- https://twitter.com/yosupot/status/1084451962060365825
- https://twitter.com/sigma425/status/1084452583022899200
- https://twitter.com/kobae964/status/1084454600042721280
- https://twitter.com/n_vip/status/1084454306743369729
- KEYENCE Programming Contest 2019 F - Paper Cutting（期待値？）
- 冪乗和を高速に求める
- 関数合成
- こっちにaddとmaxの関数合成使ってるものがある
- min,max,addは関数合成可能
- メモ
- (x-a1)^2+(x-a2)^2+...の効率的な計算方法
- (X-x1)^2+(X-x2)^2+...+(X-x_n)を展開するとnX^2-2*X*(x1+x2+..xn)+(x1^2+x2^2+...+xn^2)となり、xの総和とxの二乗の総和から高速計算が可能
- yukicoder No.1099 Range Square Sum
- (x-a1)^2+(x-a2)^2+...の効率的な計算方法
