メモ

https://atcoder.jp/contests/arc185/editorial/11160

今まで何回も見たことあるんだけど、ちゃんと分かっておらず雰囲気でやっていた部分についてを完全に理解することができたのでメモ。

$\sum_n w(n)f(g(n))$ を求めたい。これを $\sum_x f(x) \sum_{g(n)=x}w(n)$ に置き換えて計算するとき、xで累積和を取って $\sum_x h(x) \sum_{x\mid g(n)}w(n)$ とするときの、h ってなんですかという話。
まあ「右側をゼータ変換したんだから左側はメビウス変換でしょ、部分積分なんだから」という気持ちはあるし、 $\sum_{g(n)=x}w(n)$ の寄与を数えるだけでももちろん示せるんだけど、見通しよくやりましょう。

ゼータ変換(に対応する行列)を Z とし、 $\delta_k$ を k 番目の要素が1で他が0の数列とする。

$\sum_n w(n)f(g(n))\\ =\sum_n w(n)\langle f,\delta_{g(n)}\rangle\\ =\sum_n w(n)\langle Z^{-1}f,Z^\top\delta_{g(n)}\rangle$

ゼータ変換が約数側の和を取る操作であるのに対し、 $Z^\top$ は倍数側の和を取る操作になる(伝われ)ので、 $Z^\top\delta_{g(n)}$ は g(n) の約数のところだけ1になる数列である。よって

$=\sum_n w(n)\sum_{x\mid g(n)} (\mu * f)(x)\\ =\sum_{x} (\mu*f)(x) \sum_{x\mid g(n)}w(n)$

具体例

$\sum_{x\leq N}F(x)=\sum_{x\leq N}(\mu*F)(x)\left\lfloor\frac{N}{x}\right\rfloor$

$f=F, g=\mathrm{id}, w=\zeta$ として得られる。

具体例2(冒頭の問題)

$\sum_k 2^k \gcd(A_k,X) = \sum_d \phi(d) \sum_{d\mid \gcd(A_k,X)}2^k$

$f=\mathrm{id}, g(k)=\gcd(A_k,X), w(k)=2^k$ として得られる。

具体例3(約数包除原理)

$\sum_{\gcd(x,y)=1}F(x,y) = \sum_d \mu(d) \sum_{x,y}F(dx,dy)$

$f=\delta_1, g=\gcd, w=F$ として得られる

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

451
407と同じ
主客転倒で2次式の篩をしてもよい
謎の漸化式で解を生成することもできるらしい。謎ではなく互除法を逆に回すようにx=x+kyで更新する気持ち

452
ABC239H
普通にDPしてO(M^(3/4)logN)、いつものでO(M^(2/3)logN)

453
未

454
受験数学をやりすぎていると(x-n)(y-n)=n^2と変形したくなるがこれは外れ方針。
gcd(x,y)=1のケースを考えて約数包除するいつもので O(L^(3/4))
で3変数2次式の整数解を求める問題なのでピタゴラス数の列挙式のように2変数でパラメタ付けできるんですよね～と考えても同じものが得られる

455
これと同じ　F - ModularPowerEquation!!
こっちには「最大の」と書いてあるが、実はmod 10^k (k>1)だと解が一意であることが示せるので全く同じ問題になる。
証明はCRT。φを考えると2が1個増えるように思えるが、(Z/2^kZ)^*の元の位数が2^(k-2)であることを使うと示せる。

456
184と同じ
O(NlogN)

457
mod p^2ではなくmod pならmodsqrtやるだけ
mod p^2でも"pの位"が0になるようにうまくやるだけ
関連ワード：Henselの補題

458
行列累乗
直前6文字の文字種の分布を持つと203状態だが、実は「S[-i]==S[-(i+1)]となる最小のi」だけを状態に持ってもうまいこと計算できるので、状態数はσ-1にできる

459
未

460
ポワンカレの上半平面モデルを知っていますか？
知らなくても小さいdで実験すると最適解の形がわかるので、その周辺だけ見てダイクストラなりDPなり適当にやる

461
半分全列挙
2つの集合をそれぞれプラキューで取って尺取っぽくやると空間O(N)にできる

462
フック長の公式

463
和を取る対象を偶奇で分けて再帰
OEISをするとfの"意味"がわかる

464
包除原理＋zero sum rangesっぽいやつ

465
未

466
包除原理
mがでかい方から考える。さもないとnの範囲を考える必要が生じて大変(解けない?)ので。
普通に包除原理をやろうとすると集合サイズが大きすぎて困るが、無意味な要素を取り除いてminimalにするだけで間に合うらしい。
もっと効率よく集合を小さくしていくこともできるらしいが、いずれにせよ計算量は謎

467
LCS

468
rについて差分更新
S_Bを持って遅延セグ木で区間乗算をさばくのが頭を使わなくて済む方法だが、binom(n,r)の素因子をセグ木に乗せると普通のセグ木でよくなり、ノード数も1/log倍になるのでオーダーレベルで高速になる。

469
ギャグはギャグであると見抜ける人でないと(project eulerをやるのは)難しい。
N→∞のときの極限値を解析的に求めることも数学でできるので確認しておくと良い。

470
前半パート：制約が小さいので何をやっても解けはするが、ターン数から報酬の期待値への関数は上に凸であることを使うと、目の集合を固定するごとにcの昇順に考えれば全てのcについての利益の最大値をO(d)時間で求められる
後半パート：O(2^d)変数の連立方程式を解きたくなるが、よく考えると目がk個残っているときありえる集合はすべて等確率なので、結局O(d)状態にまとめられる

471
Poncelet's closure theorem - Wikipedia
知らなくても気合やエスパーなどもできる。r(a,b)さえ求めればあとの計算は簡単。

472
頑張るとエスパーできる。証明は帰納的に考えればできるらしいが、大変。
fを具体的に求めるのではなく、計算できるようにするところまでならもう少し簡単。最大値はO(log)個の区分線形であることがわかるので、あとは頑張ると計算できる。

473
Z[φ]で考えて、負のフィボナッチ数とゼッケンドルフ表現に思いを馳せると解ける。

474
素因数分解して10^5×10^6くらいのDPはすぐ思いつくが、2と5だけ別に考えることにすれば10^5は12500になるし、状態の持ち方を工夫すれば5000にもなる。
実は今回の値ではきれいな対称性があるので答えを簡単に求めることもできるが、対称性を見つけるのは難しい（証拠が与えられれば検証は簡単だが、無から見つけるのは難しい）

475
PGbattle2023せんべいD
重複を気にせず遷移して最後で定数倍して辻褄を合わせるのは頭が壊れがちなので、「index最小の人を含む組から順に決める」ことで重複カウントしないようにするという典型だと思うと良い。
計算量はO(N^4)。素直にDPすると空間O(N^4)、1つ前だけ持つやつでO(N^3)になる。
3n個の4人組から4n個の3人組を作る問題だが、適切にダブルカウントすることで逆の変換をする問題からもとの問題の答えを得ることができるので、実は時間O(N^3)空間O(N^2)で解ける。

476
マルファッティの円 - Wikipedia
貪欲で解ける。実は3個の場合は本質的に2通りの置き方しかありえないらしい

477
L - Deque
一般にO~(N)で解ける。この問題に限っては、周期性を使うことで簡単に解くこともできる。

478
未

479
対称式なので、基本対称式で書いて解と係数の関係を使う

480
DPというかtrie木の気持ちになるだけ

481
bitDP

482
未

483
制約違いがABCで既出
F - Score of Permutations
同じことをやるだけでも解けるが、いらなくなった情報を"まとめる"ことで高速化することもできる

484
multiplicative functionのprefix sumだが制約が大きい
アーベルの級数変形法のようなことをするとO(√N)になる

485
スライド最大値
Kがある程度大きいならば考慮すべきdの種類数は少なくなるので、dがでかい方から順に取っていくことでより高速になるらしいが、計算量はわからず

486
余事象
長さN>2の回文を部分文字列として持つということは、長さN-2の回文を部分文字列として持つということなので結局末尾5文字を持っておけばよく、32状態DP
漸化式を求めて解きF(n)をexplicitに求められるのであとはどうとでもなる

487
Sをfで表しておく。fをラグランジュ補間などで求めれば素数1つあたりO(k)
他の解法として、自明でないDirichlet指標の和が0であることを使うと、余った部分を愚直に計算するだけで、今回の値では高速に求めることもできる（一般には素数1つあたりO(p)）

488
実験してエスパー
非常に簡潔な必要十分条件とその非常に短い証明は一見の価値あり
なおこのゲームはWelter's gameと呼ばれ、山の個数が一般の場合にもgrundy数を求める式が知られているが、その知識をこの問題に直接役立てることは(おそらく)できない
https://www.math.sci.hokudai.ac.jp/sympo/100809/pdf/kawanaka.pdf

489
互除法によりgcdのとりうる最大値をa,bの式で表すことができるので、素数ベキごとに立方根を求めればよい。
もう少し算数を頑張ると、立方根を求める必要があるpベキは非常に小さいpのみであり愚直にやってよいことがわかる

490
f(n)はDP。f(n)の線型漸化式が得られるので当然S(n)も。
[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 | maspyのHP

491
DP

492
2乗が入った漸化式で解けるものってこれくらいしかない、ということを念頭に変数変換するとそうなる
No.613 Solitude by the window - yukicoder

493
数学で閉な式が求まる。種類数の期待値＝Σ各種類が含まれる確率

494
未

495
分割束上の包除原理。maspyさんの資料が詳しい
mobius - Google ドライブ

496
幾何の問題を代数の問題に帰着するところまでは高校数学
あとは適当な制約の下でxx=yzの解を数えることになるので、gcd(y,z)を考えて包除するとO(N)
より高速な解法(3/4乗だか2/3乗だか)があるらしいがよくわからず……

497
棒から棒への移動の回数と1回あたりの期待値が求まれば良い。前者は自明
後者はxからx+1に移動するまでの期待値がわかればよく、xの昇順に考えると求まる

498
y=x+1と変数変換すればあとは閉な式を得るところまでは簡単
値がいい感じなのでLucasの定理をそのまま使って良い

499
未

500
高度合成数を作るときと違って、素数ごとに約数の個数が2ベキでなければならなず、独立に考えてよいため貪欲でよい

メモ

yukicoderでゆるふわgolf

Project Eulerで全実績解除までにやったこと

買って良かったもの(2025)

スマホ

遮光カーテン

棚

買ってよかったもの(2019-2025)

掃除機

洗濯物干し

セームタオル

冷蔵庫

電子レンジ

電気ケトル

机と椅子

約数包除2

Project Euler 451-500 解説