これの続き
sugarknri.hatenablog.com
501
prime countingでO~(N^(2/3))
502
DP方針から、累積和でO(HW)、行列累乗でO(H^3logW)はすぐわかるが、最後が難しい。
偶奇の条件を忘れたときの答えはH^W-(H-1)^Wなので、Hを動かすとどうなるかはなんとなく想像できる。証明は縦にDPする方針で帰納法を使えばできる。
503
B - せんべい
気持ちはこれ。これをそのままやると2乗になるので、算数をして線形にする。
504
ピックの定理 全探索O(m^4)
a,b,c,dの全探索ではなくb,d,a+cの全探索をすることにするとO(m^3 logm)になると主張されているが計算量解析は不明
505
未
506
周期性
507
絶対値がついている問題は絶対値を外すとよい……と言いたいところだが、もしそれで解が存在したら最小値は0になるということなので、結局最小値を取るのは領域の境界であることがわかる。
実はベクトルに対してそのまま互除法のようなことをやる極めて単純なアルゴリズムがある。
508
桁DP
i(i-1)^2=2
509
実験するとgrundy数がわかる。証明は帰納法
510
Descartes' theorem - Wikipedia
あとはいつもどおりgcdを新たな変数に置いて整理すると生成式が出てくる。
計算量は普通にやって ？ SB木でgcdの計算を回避すればlogは消せるはず
511
いつものDP高速化
素因数分解を除いて
512
fがmultiplicativeなのでO(N^2/3)
513
中線定理
積=積の形に整理して全探索可能
2x^2+2y^2 = (x+y)^2 + (x-y)^2 なんですね～
包除原理とfloor sumでO(NlogN)になるらしい（未確認）
パラメータにより解を記述することもできるらしい。原理は謎
514
ピックの定理を考えてもいいし、単に多角形の面積を求めるやつの主客転倒をやるだけでもよい。
多少適当で6乗くらいのアルゴリズムにはなるので解くだけなら簡単。ちゃんと詰めると4乗くらいになる
めちゃくちゃ頑張ると2乗にもなるらしい
515
主客転倒で n^-1 が何度寄与するかを考えると解ける。エスパーでも解ける
516
totientは乗法的関数なので素因子ごとに考えて良い
smooth numberは少ない
517
グリッドの問題だと思うのがわかりやすいと思う
518
3項の等比数列は必ず (kxx, kxy, kyy) と書ける
519
斜めにDPするO(N^2)を累積和で高速化してO(N^1.5)
520
DPを行列累乗で高速化
521
Lucy DP
522
主客転倒
グラフが与えられたときの最適な操作を考える
523
前から順にソートされるので、末尾に1つ値を加えたときの挙動を観察すると解ける
524
同上
525
曲線を媒介変数表示して数値積分
526
適当に小さい素数を篩えばよい。
例えばmod720720だと次点解との差が0.5%くらいあるので、逆転できない解が見つかれば十分。
527
B(n)は自明。R(n)は漸化式を解く
528
最近だとFPSで解くのが流行りか。普通に包除してもいい
529
和風いろはちゃん＋行列累乗orBM
530
sum(gcd(x,y) where xy<=N) だと思って約数包除 O(N^1/2 logN)
multiplicativeなので殴っても実行時間はたかが知れている
531
はい
532
未
シミュレーションするとなんかバグる カス
533
f(k)=max {n | λ(n)|k} ととしてλ(p)を配ればよい
O(NlogN)
534
DPやるだけ
N-Queen問題くらいもちろん皆さん実装したことありますよね？
535
最後に丸がついた数をにぶたん
536
mが満たすべき性質を適当に求めたあと、m/lpf(m)を全探索すると早いらしい
537
FPS pow
ナイーブな多項式乗算、あるいはダブリングだと思っても許される制約
538
4辺が与えられた四角形の面積の最大値を求める公式は存在する。
雑に「上位N個からC(N,4)を全探索」でも解けるが、辺を追加するごとにチェックする必要がある四角形は高々4個であることが示せる。
O(N)
539
1ステップ進めることを考えるとPの再帰式が得られる
O(logN)
540
列挙式を思い出して約数包除でO(N^1/2logN)
凸包テクでO(N^4/9)にもなる
541
p進付値に思いをはせる。
ord_p(1/n)が小さいところの和がいい感じになっている必要があるので、p進で上の桁から全探索
542
公比は(x+1)/xだけを考慮すれば十分なので、setwise coprimeな等比数列はO(√N)個
最大にならないものを枝刈りをすると大した数は残らないので、あとは適当に。
プラキューで順番に生成することもできる
543
ゴールドバッハ予想
544
彩色多項式＋多項式補間
545
OEIS
Von Staudt–Clausen theorem - Wikipedia
546
動的imosで上から普通に再帰するだけ
組み合わせ的な言い換えによりデジタル冪級数に帰着して機械的に解くこともできる
547
数学を頑張るとO(N^4)でできる
数学を頑張らずに、適当な前計算により図形1つあたりO(N^2)で計算するO(N^6)解法もある
548
g(n)はnの指数のみによって決まるので全探索
549
素数べきに分解してord_p(n!)を求めるいつもの
550
grundy数が小さい
