これの続き
sugarknri.hatenablog.com
何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ
401
主客転倒でO(√N)
D - Sum of Divisors
凸包テクでO~(N^(1/3))になるらしい。1乗のときの解説はここ
凸関数に囲まれた領域の中の格子点の凸包の頂点を列挙する一般的なテク - 競プロをはじめた家事手伝いロボットのブログ
402
定義からM(a,b,c)|gdc(f(1)-f(-1),f(2)-f(-2))であり、ある定数Xが存在してgdc(f(1)-f(-1),f(2)-f(-2))|Xなので、S(n)はn%Xごとにn/Xの3次式
403
数学をすると交点の座標が整数になることがわかるので、変数変換してすべてそれで考えることにすればO(√N)で計算できる式になる
404
数学をかなり頑張るとa,b,cが満たすべき数式が出てくる。直交座標よりも極座標で考えた方が簡単
でてきた式を整理すると「p^2+q^2=hogeの有理点を列挙せよ」といういつものやつに帰着できて解ける
405
実験してエスパー
証明は「辺を共有する2つの畳の位置関係は4種類しかないので、それらが次の1ステップでどうなるか観察する」
406
答えを二分探索
「二分木の左に潜るにはコストa、右に潜るにはコストbかかる。コストx以内で到達できる頂点の個数は？」
407
(Z/nZ)^*の構造を知っていますか？
CRTで素ベキの場合に帰着。mod 2^eでe>2のときだけ2解あることに気を付けて、あと全探索
408
Y - Grid 2
409
dp[m]=山の個数がmのとき条件を満たす組み合わせ
で実は求まる。遷移は……？
410
未
411
セグ木で平面走査
412
知識ゲー
Hook length formula - Wikipedia
413
桁DP。gcd(10,d)!=1のときに注意する
テクい状態の持ち方をするとO(N^2 2^N)にもなる。
数Xが条件を満たす必要十分条件は、「∃! i (∃j s.t. X[i:j]はNの倍数)∧(∀i'≠i ∀j X[i':j] はNの倍数でない)」である
（読者への宿題：∃!i∃jのところが∃!i∃!jでなくてよいことの証明）
この条件を満たす数はiを固定するごとにdisjointであるから、iごとにO(N 2^N)で数え上げられる。
threadには「NFAをこねこねするとこのDPになる」と書かれているが、よくわからず。
関連：NFAをDFAに変換するやつ
Powerset Construction DPについて • knshnbのブログ
414
未
415
未
416
DP＋行列累乗
俺の中ではこれの類題としてジャンルになっているが、このDPに名前がついているのを聞いたことがない
No.213 素数サイコロと合成数サイコロ (3-Easy) - yukicoder
417
10のでの位数を求めてください、という問題なので399のより簡単なバージョン
O(NlogNloglogN)くらい？
418
制約がN≦10^14ならここに
No.376 立方体のN等分 (2) - yukicoder
a,b,cいずれもをN^(1/3)くらいにとるのが最適なので、N^(1/3)付近の約数をあらかじめ列挙してaを枝刈り全探索
419
Look-and-say sequence - Wikipedia
頑張って観察すると自力でも気づけるらしいが、それはもうコンウェイなんだよな
420
2×2行列の平方根という概念を使ってもいいが、適当に数式をガチャガチャやるだけでも解ける。
Square root of a 2 by 2 matrix - Wikipedia
421
「n^15=-1 mod mを解いてください」という問題なので、407と同様。
原始根を求めなくても、x^5+1が因数分解できるので、平方根だけで直接計算することもできる
422
未
423
「n回投げてちょうどm個」は一発で計算できるので、最後の1回を追加してどうなるか差分更新をやるとO(NlogN)
424
96の数独のように手でも解けます
俺はSAT solverを用意するのを面倒がってIP solverに投げたがそれでも解ける
普通にバックトラックDFSでも解けるっぽい？
425
UF
ダイクストラでも解ける
426
問題タイトルが答え
「箱玉系」でググって出てくる日本語論文に目を通すと答えが書いてあるが、証明はわからず
十分間隔が広い箇所で2つに分けて再帰的に処理することでも解けるらしいが、証明はわからず
427
未
428
概念はこれ
Steiner chain - Wikipedia
数式はこれを使うのが簡単
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1843-17.pdf
証明はこれでできるらしい
反転幾何学 - Wikipedia
あとは丁寧に式を整理すると空間O(N)時間O(NlogN)までは簡単
ちょっと変な形をしているが、少し考えるとい つ も のに帰着できて、O~(N^(2/3))になる。
429
自明
ルジャンドルの定理など
O(NlogN)。線形篩でO(N)になる？
430
期待値の線形性
二項定理
小さすぎる値は無視して近似してよい。近似を使わずに(計算精度を度外視すると)O(M^2)で求めることもできる
431
気合で数値積分＋二分探索
432
totient sumとほぼ同じ
dirichlet級数の練習問題だと思うこともできる
いずれにせよO~(N^(2/3))
433
未
434
グリッドを見たら二部グラフだと思え、の格言に従って考察すると解ける
O(N^4)
435
行列累乗やるだけ
CRT+pisano periodでも解ける
436
2変数積分方程式を立てて頑張って計算すると手ですべて解ける
確率密度関数を直接求めに行く方針でも手で解ける
437
原始根よりもfibonacciの条件の方が強いので、fibonacciの条件を満たす数を求めてから、それが原始根かどうか判定する
mod_sqrt
438
未
439
最終的にきれいな式がでてきて い つ も の でO~(N^(2/3))になる
いろいろ考え方はあるが、σ(ij)が乗法的ではあるが完全乗法的ではないことから、そこの違いを解消するように包除原理をするとよい。
具体的にはなので、これをp partごとに考えて包除すれば
を得る。
他にも例えば なるfを気合で求めるなど、いろいろやりようはあるのでまあやれば解ける
440
T(n)ではなくfibonacci数だとどうなるか考えると、Tも似たような漸化式を持つので似たような性質を持つだろうと予想できる
あとはこまごました計算をすればOK
441
coprimeと書いてあるので約数包除
o(NlogN)にするには多くの方針で1/xy=(1/x+1/y)/(x+y)を使ってうまく式変形することが求められる
調和数を適当に近似してO(1)で求めることにすれば い つ も の でO(N^(2/3))にもできる
包除で引き算やってて精度保証を机上でやるのはもう無理。単にO(Nε)で見積もっても、拡張倍精度でεは2^-63≒1e-19、N=1e7、要求精度が1e-11だから結構怪しい。めちゃくちゃ
442
桁DP＋にぶたん
「与えらえた文字列を部分文字列に持つような長さNの文字列を求めてください」ならKMPなりtrieなりSAなりで適当にやるとDPできる
あとはそれの直積を状態に持てばよい
制約が小さいのでかなり適当にやっても解けるらしい
443
gcd=1のところをまとめて処理すると実はめちゃくちゃ高速になる
計算量は謎
444
最適な戦略がわかれば、E(n)を求めるパートは期待値の線形性典型
E(n)からSk(n)を求めるパートは適当に近似計算すればよい
445
関数方程式を整理するとa,bが満たすべき条件が得られる
a,a-1が互いに素であることに注意すると、aとしてあり得るものの候補が決まり、bが満たすべき条件もわかる
あとは差分計算。計算量は雑にやるとO(NlogNlogMOD)、logMODを落とすいつもの工夫をするとO(NlogN+NlogMOD)にできる
446
n^4+4が整数係数の範囲で因数分解できるとかいう受験典型テク
あとは445でした考察と2次式の篩をすればOK
447
multiplicativeなので3/4乗、普通に約数包除すれば実は1/2乗
ゼータ関数で書けるので2/3乗にもなるが、約数包除の立式を経ずにたどり着くのは難しそうに思える
448
gcdの値ごとに和を取ることにすると、ほぼtotient sumになる。O~(N^2/3)
449
気合で座標計算したり、解析学の定理を使って頑張ったり、Minkowski–Steiner formulaを使ったりと、厳密解を求める方法はいろいろ解法はあるらしいが、適当に点を取って数値計算するのが一番簡単っぽい
450
未
