これの続き
sugarknri.hatenablog.com
「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。
151
DP
152
1/kpを使ったら、pがどこかで約分される必要があります
バックトラックDFSで全探索
指数でも分けたらもっと早くなるらしい
153
主客転倒でO(N)
計算式をよく見ると、totient sumのようにgcdで除原理をするやつ＋Dilichlet convolutionでできるのでO(N^(3/4))
さらに、除原理する前のパートの計算を、上は格子点数え上げ、下は愚直でO(N^(2/3))にできるので全体でO~(N^(2/3))
格子点の数え上げの高速化 - memo
154
雑にやるとO(N^2logN)とかだが早い言語なら間に合う
以下の記事の真ん中らへんに書いてある「補題」を念頭に、5進digitsumで分類しておくと定数倍の小さいO(N^2)になる
クンマーの定理とその証明 | 高校数学の美しい物語
155
n=k+(n-k)です
分母が小さいことが帰納的に示せるので、setではなく表で持つとlogがおちて数十倍早くなる
156
2000未満に1は1600回登場して、2000～2999に1は300回しか登場しないので、2000≦n≦2999の範囲にf(n,1)=nの解は存在しません
そんな感じで間を飛ばすと間に合う
157
108でやった
158
手で解けます
No.411 昇順昇順ソート - yukicoder
159
DP O(NlogN)
160
n!/5^k mod 5^5みたいなのを求めたいですね。5の倍数だけ避けて再帰的に計算すればよい
ウィルソンの定理を使うと手抜きができる部分もある
類題は592
こういうのもある。この問題でここまでする必要はないが……
二項係数 mod Prime Power - memo
161
DP O(6*4^NNM)
F - Hanjo 2
162
包除原理 手で解け
163
Nが小さいので多項式時間なら何やっても許される
2点選んで全探索するのが一番簡単そう
O(1)でも解けるらしい
164
DP
165
幾何
166
条件式がrank8なので、8つ決めれば一意
167
もしこの問題に対する証明を自力で与えることができたなら、あと30年早く生まれていれば論文になりました。おめでとう
問題を解くだけであれば、実験してエスパーするか、wikipediaに書いてある本質情報を使う。
証明を理解したいのであれば、[1]のtheorem1と[2]のtheorem2を組み合わせると、LFSRに帰着されることからわかります（！？）
[1] https://core.ac.uk/download/pdf/82710604.pdf The Regularity of Some 1-Additive Sequences, JAMES SCHMERL AND EUGENE SPIEGEL
[2] https://www.mathstat.dal.ca/FQ/Scanned/29-3/finch.pdf CONJECTURES ABOUT s-ADDITIVE SEQUENCES, Steven R. Finch
168
誰でも一度は考えたことがあるはず
10N+dとおいてやるだけ
169
ド典型 O(logN)
D - Number of Multisets
170
どっちを全探索するか迷うところだが、少し考えると乗数の候補がかなり絞れることがわかる
171
DP O(B^3(logN)^2)
mod998244353ならFPSのlog,expで O~(B^2logN)
172
DP O(B^3logN)
EGFを考えても解ける
173
2変数で条件式が1本あるので、全探索 O(√N)
174
173で出した式をそのまま使う O(NlogN)
自明な改良をするとO(N)になる
175
169で作った漸化式を思い出して、同じように漸化式を作る
176
因数分解するだけ
偶数のときはparityが壊れないよう気をつける必要があるという細かい罠がある
177
幾何
全探索するだけ
回転一致・対称一致に注意
178
DP
部分集合やminmaxを持ちたくなるが、そこまでは必要はないのでO(BlogN)
179
やるだけ O(NlogN)
線形篩でO(N)
180
ギャグ
式変形する
181
DP O(B^2 W^2)
適当な順にソート
182
乗法群(Z/nZ)^*の構造を知っていますか
183
連続緩和(?)
184
偏角ソート＋2点決め打ちでO(r^4)
その時の和がどういう形になっているかよく見るとO(r^2)
gcdを引いていくいつものやつでsublinearにもなるらしいです。こわい
185
現代の計算機は早いので適当に探索してもわりと間に合う
整数計画問題だと思ってそのへんのIP solverに投げてもいい
186
UF
187
そのまま篩ってO(NlogN)
いつもの素数カウントのやつでO(N^(3/4)/logN)とかにもなる
188
Library Checker
189
遷移がだるいDP
190
ラグランジュの未定乗数法を使うな
AM-GM典型だぞ
191
DP
192
連分数
計算量は悪いがStern-Brocot treeで愚直にやっても間に合うらしい
何ステップ連続するか求めて間を飛ばせば同じ計算量になるが、精度に不安あり
193
ディリクレ級数を考えるとO(N^(2/3))
Dirichlet 積と、数論関数の累積和 | maspyのHP
メビウス関数の性質を使うとO(N^(1/2))
https://twitter.com/37zigen/status/1460288422015242241
さらに商でまとめるテクでO(N^(2/5))
[1107.4890] Counting Square-Free Numbers
194
DPをしようとすると本質に気づきDPはいらないことがわかる
え？何が本質かわからない？しょうがないにゃあ
https://kokiymgch.hatenablog.com/entry/2018/01/27/235959
195
60度の三角形の生成式は143で見た
生成パラメータの探索範囲は初等幾何で示せばO(NlogN)
いつものようにO(N^(2/3))になるらしい。2変数でもできるんだ……
196
区間篩
197
これは実験＋エスパー以外の解き筋ないです
198
Stern-Brocot tree
左端を適当にまとめると早くなる
1/102みたいなのを数え忘れないように(1敗)
200
プラキューでp^2q^3を小さい順に生成してもよし
N以下のそういう数はO~(N^(2/3))個しかないので(区間ごとに)雑に列挙してもよし
