これの続き
sugarknri.hatenablog.com
何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ
351
Dirichlet convolutionでO~(N^(2/3))
Dirichlet 積と、数論関数の累積和 | maspyのHP
これくらい単純ならDirichlet級数に思いを馳せなくても普通にDPだと思うこともできる
トーティエント関数$\varphi(i)$の和$\sum_{i=1}^{N}{\varphi (i)}$を$O(N^{2/3}(\log\log{N})^{1/3})$で求める Wiki - yukicoder
最近中国奥地でO~(N^0.5)が開発されたらしい（未確認）
https://twitter.com/EI_Captain/status/1678956489468428289
352
DPでT(N,p)がO(N^2)
353
大円距離 - Wikipedia
354
格子が正方形の問題は233で見た。これはZ[i]で素因数分解する問題だった。
格子が六角形だとZ[ω]で素因数分解する問題になる
355
Set packing - Wikipedia
IPなので、IP solverに投げると解ける
356
318で見た
証明は増減表を書くとわかる
357
予め素数を列挙しておいて、dでループすると調和級数でO(NlogN)
358
Cyclic number - Wikipedia
この性質を持つ数が1/pの形に限ることをちゃんと証明しましょう。あとは自明
359
実験
360
mod2を考えて定数倍削減
主客転倒。x座標の値がiであるような点の個数が各iでわかればよく、233と同じ
361
未
362
DP[i][S]=i以下の数のみで、S以下の数を分解する方法の数
とすると素数カウントと同じDPになるのでO(N^(3/4))
363
ベジェ曲線 - Wikipedia
曲線のx,y座標がtの3次式、vの1次式で書けることがわかる。
面積はvの2次式で書けるので、求めるvは一意に定まる。
曲線の長さは∫√(tの4次式)dtの形になるので数値積分
364
O(N)
ステップ1で選べる席が全て埋まった状態が与えられたとき、残りを埋める方法が何通りあるかは簡単。
ステップ1で選べる席が全て埋まった状態が与えられたとき、その埋まり方になる方法が何通りあるかは簡単。
ステップ1で選べる席が全て埋まった状態とは？
365
Lucasの定理＋CRT
366
O(logN)
Fibonacci nim - Wikipedia
367
吸収マルコフ連鎖の期待値を求めるいつもの問題。状態数を11!から減らす。
ソートアルゴリズムの気持ちになるとfunctional graphが同型なら状態として等価なことは明らか
368
桁DP。かなりびっくり
Kempner series - Wikipediaに"Schmelzer and Baillie found an efficient algorithm for the more general problem of any omitted string of digits. "と書いてあり、ここに解法が載っている。
369
bitDP
DP[i][n][S]=1〜iまでの4i枚からn枚選んで、n枚から相異なる数を選んだときのマークの集合({0,1}^4)としてありえるものの集合(2^({0,1}^4))がS
スートがC種、数がSまでとして、O(2^2^C*2^C*S*N)
対称性を考慮してさらに改善できるらしいが、頭を使わずに済むのはこのあたりまでか。
370
丁寧に考察すると、これになる
約数包除原理 - メモ
O~(N^(2/3))
制約がでかいのでO(N^(3/4))だとちょっと時間がかかる
371
(1,999),(2,998),…のペアを引く問題だと思うと、dp[n]=すでにn枚見たときの残りの期待値、というDPができそう。
あとは0と500を適切に扱えばOK
372
floor(y^2/x^2)が取りうる値の範囲は(N/M)^2以下なので、
それぞれについて傾きを有理数近似してsum_of_floor_of_linear
373
未
374
O(N^0.5)
実験
証明は「そうでないなら変更しても損しない」
375
周期性
Rを全探索して最大長方形みたいなことをしてもいいし、主客転倒してもいい
周期性をもつという事実からM(nq+r)がrを固定するごとにqの2次式になることがわかるので、愚直＋多項式補完でもいい。
376
挿入DP
目を座圧して持つとさらに加速する
377
桁DP+行列累乗
378
nとn+1は互いに素なのでdTを求めるのは簡単
残りは真ん中を全探索するいつもの
379
みたいなものが求めるもの
約数包除すると∑N/(xy)みたいなものを求めたくなって、これを「(x,y,z)の組でxyz≦Nとなるものはいくつ？」みたいに読み替えて、x,y,zの大小関係について丁寧に場合分けすると愚直がO(N^(2/3))になる。
Dirichlet級数で解釈して一発でできるかはわからず。floorが入ってるのでどのみち言い換えをしないと難しそう
380
行列木定理
scipyに丸投げすると解いてくれる
実はきれいな式が存在する
381
ウィルソンの定理
S(p)=-3/8なのでpのmodで適当に場合分けすると1次式になり、いつものでO(N^(2/3))になる
……threadにはO(N^0.75)しか書かれてないけど、なるよね？？
382
与えられたsetが条件を満たすための必要十分条件はmax < sum-max
S[n]を使うかどうかで再帰的に場合分けすると漸化式が得られるのであとはいつもの
383
桁DP
O( (logN)^2)
384
未
385
未
多分これ
Marden's theorem - Wikipedia
386
Antichainの最大サイズを求めたいので、Dilworthの定理を思い出しつつ、2次元の場合に思いを馳せると斜めに切るやつを思いつけ、一般の次元でもそれが答えになることがわかる。
あとはosk_a法でO(NlogN)
いつものDPでO~(N^(3/4))だかO~(N^(2/3))でも解ける
387
DFS+ミラーラビン
388
351の3次元版なので、351と同様に解ける
389
算数をすると手で解ける
もちろんDPをしてもいい
390
ヘロンの公式を使うと一般Pell方程式になる
実はこの形の場合、初期解が自明なものに限ることが示せるので、適当にやっても解ける
初期解が自明なものに限ることの証明は自明ではない
391
未
392
目的関数が凸なので、山登りのようなことを収束するまでやればよい
393
連結性DP
289などでやった
394
積分方程式を立てて解くだけ
Cauchy–Euler equation - Wikipedia
積分方程式を数値計算で解こうとすると精度が厳しいと思う（俺は最後の1桁が求められなかった）
395
適当に端っぽいところだけ持ちながらやれば解ける
厳密にやるには考察が必要。i回目のイテレーションで追加される正方形のサイズはi+1種類であり、同じサイズの正方形は同じ向きになるので、サイズごとに座標を持てばO(iter^2)
396
k進法で考えたときの下の桁から消していけばよい
べき乗のmodをいい加減に扱っても正しい答えが得られてしまうので要注意
397
未
398
2番目ではなく1番目なら主客転倒やるだけ（例：表が出るまでコイントスするときの回数の期待値は？→1+1/2+1/4+…=2）
2番目のときもほぼ同じ
ところでFPSで解釈しても解ける。期待値を求めるというのは実質数え上げなので。
399
問題文にヒントが書いてある
No.3038 フィボナッチ数列の周期 - yukicoder
400
DP
Hackenbush - Wikipedia
