メモ

yukicoderでゆるふわgolf

FPS

この記事を書いた4時間後に以下の記事が公開されました。これを読もうね-完-
maspypy.com

以上で本質情報は終了です。ありがとうございました。以下はおまけです。


まえがき

この記事を読んでも競プロに強くはなれませんよ。
FFT多項式乗算が高速にできる原理をしらなくても、FFTを実装すれば多項式乗算ができるのと同じです。

カジュアルな定義:"足し算"と"掛け算"が定義されている集合を環という。
もうすこし正確な定義:集合と"足し算"と"掛け算"の3つ組を環という。(同じ集合に対して、違う"足し算"と"掛け算"を定義して、違う環を作ることもできるので)
本当に正確な定義:wikipediaでも読んでろ→環 (数学) - Wikipedia
ここでいう"足し算"と"掛け算"はそういう名前の二項演算のことであって、別に足し算と掛け算のことではない。でも足し算と掛け算みたいな性質(例:分配法則)が成り立っていることを要求する。
さらに、"足し算"は暗黙のうちに"引き算"ができることを要求する。"掛け算"は別に"割り算"ができることを要求しない。

例1

整数全体の集合に、+を"足し算"、×を"掛け算"と定めたものは環になる

例2

0以上M未満の整数全体の集合に、mod Mでの足し算を"足し算"、mod Mでの掛け算を"掛け算"と定めたものは環になる

例3

uint32で表すことができる数全体の集合に、bitwise xorを"足し算"、bitwise andを"掛け算"と定めたものは環になる

例4

0以上2^2^N未満の整数全体に、bitwise xorを"足し算"、Nim productを"掛け算"と定めたものは環になる
これは例2と同じ集合に別の演算が入る例でもある

例5

0以上の整数全体の集合に、minを"足し算"、+を"掛け算"と定めたものは環ではない。minは"引き算"ができないので。ちなみに、環の定義から「"引き算"ができる」を抜いたものを半環という
(余談:半群は単位的とは限らないのに半環の加法群は単位的なんですね~)

例6

整数を成分とする2×2の正方行列全体の集合に、成分ごとの和を”足し算"、行列積を"掛け算"と定めたものは環になる。ただし、この環は掛け算が可換でない。つまり、"掛け算"を×であらわしたとき、A×B=B×Aが一般には成り立たない。
"掛け算"が可換な環を可換環といい、可換でない環を非可換環という。
可換環、直感に反するので困るんだよね。そういうのは面倒なので、以下この記事では単に環と言ったときは可換環を指すものとする

形式的べき級数

定義:数列(a_0,a_1,a_2,\ldots)のことを形式的べき級数(FPS)という。
多項式? 不定元X? なんの話ですか? べき級数というのは数列のことですよ。

形式的べき級数

次で定義される環を形式的べき級数環という。
集合:全ての数列からなる集合\{(a_0,a_1,a_2,\ldots)\}
"足し算":(a_0,a_1,a_2,\ldots)+(b_0,b_1,b_2,\ldots)=(a_0+b_0,a_1+b_1,a_2+b_2,\ldots)
"掛け算":(a_0,a_1,a_2,\ldots)*(b_0,b_1,b_2,\ldots)=(c_0,c_1,c_2,\ldots) としたとき、c_i=\sum_{k=0}^{i}a_kb_{i-k}
数列の話をしてたのに急に本性表してきたなこいつ。
"足し算"と"掛け算"の定義をみるとわかるとおり、数列A:=(a_0,a_1,a_2,\ldots) に対して、不定元Xを用いた無限級数f_A(X)=a_0+a_1X+a_2X^2+\ldotsを対応させると、この"足し算"と"掛け算"は無限級数の足し算と掛け算だと思うことができるんですね~。あーあ、せっかく数列の話ってごまかしてたのに。そういうわけで以下ではFPS不定元Xを用いた無限級数を用いて表します。無駄な努力だったな……。
ところでもちろん、数列の各要素に対しても"足し算"と"掛け算"が定まっている必要がある。つまり、FPS環を考えたいなら数列の要素はなんでもいいというわけではなく、それもまた環の元である必要がある。要素が環Rの元であるような数列の集合から作ったFPS環のことをR[[X]]と書く。このとき、RR[[X]]の係数環という。

例1

上の方でやった、整数全体に普通の足し算と普通の掛け算を定めるやつ、あれのことを\mathbb{Z}と表す。(単に集合としての整数全体をさすことももちろんあるけど、環として考えますよというのを強調しています)
\mathbb{Z}[[X]]は整数係数のFPS環である。

例2

上の方でやったmodMのやつのことを数学では\mathbb{Z}/M\mathbb{Z}と書きます。(この記法はふつう剰余環を意識したものなので、上でやったことを定義とするわけではないけど、できるものは同じなのでここでは気にしないことにしましょう)
(\mathbb{Z}/M\mathbb{Z})[[X]]は係数をmod Mで考えるFPS環。

環の乗法逆元

乗法逆元の話をするまえに加法逆元の話を思い出しておこう。
"引き算"というのは、二項演算ではなく、単項演算だったんですよね(!?)
どういうことかというと、xに対して、x+y=0となるようなyのことをxの加法逆元といい、-xと表して、一般にa-bというのはa+(-b)のことだった、という話です。
これを踏まえて乗法逆元の話を考えてみる。環の"掛け算"は"割り算"ができる必要はないといったが、6/-1=-6のように、できることももちろんある。
定義:xに対して、x*y=1となるようなyのことをxの乗法逆元といい、x^{-1}と表す。
一般にa/bというのはa*b^{-1}のことだった、ということになるわけですね。
(この説明にはちょっとごまかしがあって、例えば\mathbb{Z}において6/2を「2x=6となるx」として定義する感じで、部分的には二項演算としての割り算ができることもあるんですが、そういうのは考えません)
主張:乗法逆元は存在すれば一意。
証明は各自
定義:乗法逆元が存在するような元のことを可逆元という。

例1

\mathbb{Z}の可逆元は \pm 1

例2

\mathbb{Z}/9\mathbb{Z}の可逆元は1,2,4,5,7,8
(わかってる人向けのエクスキューズ:同値類だから整数そのものじゃないとかいう難しい話を初心者にするのはやめよう!だってここで同値類の定義してないし)

例3

\mathbb{Z}[[X]]の可逆元はなんでしょう?
答え:定数項が\pm 1であるような全ての元
なんで?
1-Xの乗法逆元を求めて見よう。そのようなものが存在するなら、定義から
(1-X)(b_0+b_1X+b_2X^2+b_3X^3+\ldots)=1となる。
次数ごとに左辺と右辺を比べてみよう。
定数項:1*b_0=1b_0=1
1次の項:1*b_1+(-1)*b_0=0b_1=1
2次の項:1*b_2+(-1)*b_1=0b_2=1

ということで、以下帰納的にb_i=1と求まる。つまり(1-X)^{-1}=1+X+X^2+\ldotsとなるということ。この求め方をぐっと睨むとわかってもらえる通り、定数項が1であるようなFPSの逆元を求めようとすると1*b_n+a_1*b_{n-1}+\ldots=0という形の方程式を解いてb_nを求めることになるが、これはnの小さい順にやると自明。

??

この話って要するに、実数の逆元を考えている時に、「1÷7は0.142857……と必要なだけ計算することができますね。だから逆元は存在するんです!」と同じ論法をしている。間違ってはないんだけど、その「……」ってどういう意味やねんという話になります。いやなるかどうかはしりませんが、俺はなったので、きっちりやっておきましょう。
「可逆なfとその逆元gに対して、帰納法で任意のnについてgのn次の係数を一意に決定することができ、このとき任意のn>0に対してfgのn次の係数が0になることを具体的に計算できる。証明終わり」めでたしめでたし。いやー、収束がどうこうとかいう話をする必要があるのかと思って一瞬焦った。ちなみに例に挙げた実数の逆元の話のときは、繰り上がりとかいう概念のせいで同じ論法ではうまくいかないので収束がどうこうとかいう話をする必要があります(多分)

主張:FPS環の元は、定数項が係数環の可逆元であるとき、かつその時に限り可逆である。
証明は各自

有限項で打ち切る話

コンピューターは有限しか扱えないので、(1-X)^{-1}すらナイーブには表すことができません。
でも実数を「1÷7は……うーんまあ0.142857で近似すればいいかw」と計算するように、FPSもn次の項までで打ち切って近似計算できます。
実数だと誤差評価は面倒な話ですが、FPSのときはn次の項で打ち切ってFPS環の計算をするとn次の項までの精度があり続けます。繰り上がりがないのでね。
本質的には、「整数\mathbb{Z}をmod Mの世界\mathbb{Z}/(M)に持っていってもコンパチ」というのと同様に、「FPSR[[X]]を有限項で打ち切ってR[[X]]/(X^n)に持っていってもコンパチ」という話なんですけども。

exp

定義:有理数を含む環を係数とするFPS環において、定数項が0であるようなの元fに対して、\exp(f)=\sum_{i\geq 0}\frac{1}{i!}f^iと定める。
有理数を含むという条件は、要するに1,2,3,4,…での割り算ができますという意味です。
この定義式は\exp(X)=1+X+\frac{1}{2}X^2+\frac{1}{6}X^3+\ldotsというおなじみの式を導きますが、あくまで定義であって、実関数e^Xマクローリン展開とはなんの関係もありません。
行列Aに対してexp(A)を考えるのと同じで定義です。
(同じ名前がついている以上、本当になんの関係も無いわけではないですが、実関数の常識は忘れましょう)
余談:定義域は「定数項が0」ほど厳しい必要はなく、「定数項が冪零」でいいと思うんですが、まあ面倒なのでここでは0にしておきましょう。
\mathbb{Q}を含んで、かつ0でない冪零元が存在するような環の例としては\mathbb{Q}[t]/(t^2)があり、(\mathbb{Q}[t]/(t^2))[[X]]において\exp(t)=1+tとなります。

exp(1)

「『定数項が0であるようなFPSの元fに対して』←??? \mathbb{R}[[X]]上では\exp(1)=eだし、定数項があっても大丈夫じゃん」
大丈夫ではありません。……という話がしたいんですが、この話をするためには収束がどうこうとかいう話をする必要がある。さっき頑張って回避したのに、結局やらなきゃだめなのか……

お断り

以下、うっかり付値環の話をしてしまったので、係数が体でないと話が通らなくなってしまいました。ということで以下では係数は体です。
"付値"という言葉を使っているものの、付値の性質は完備性しか使っていないので、それを別に証明すれば環を係数とするFPS環でも同様にいえます。というかここでは完備性の証明はしていないので全部一緒です。
他にも\{f+(X^n)\}を開基とする位相を入れて(距離空間ではなく)位相空間での収束を考えてもいえるみたいです。

証明の準備

expの話がしたいだけなので、expの話ができるギリギリまでいろいろ省略
定義:体\mathbb{F}を係数とするFPS\mathbb{F}[[X]]に対して、付値\nu:\mathbb{F}[[X]]\to\mathbb{Z}_{\geq 0}\cup\{\infty\}を、\nu(f)=\min\{n \mid f \text{のn次の係数が0でない}\} と定める。このとき、FPS環の元f,gに対して、その距離をd(f,g)=2^{-\nu(f-g)}で定める。
なんのこっちゃねんという感じですが、要するに「低次の項がいっぱい一致してたらだいたい一緒」という気持ちです。「0.12345……と0.12489……は2桁目まで一致してるから、距離は10^-2くらいかなーw」というのと同じで「1+2X+3X^2+4X^3+5X^4+\ldots1+2X+4X^2+8X^3+9X^4+\ldotsは2つ目の項まで一致してるから、距離は2^-2くらいかなーw」という気持ちです。
定義:距離空間の元の列a=(a_1,a_2,\ldots)に対して、\lim_n d(x,a_n)=0 が成り立つとき、aはxに収束するという。また、あるxが存在して数列aがxに収束するとき、aは収束するという。
無限に近づくなら収束、という普通の定義。これはFPS環とか関係なく、距離空間のお話です。
定義:体係数FPS環における収束は、付値によって定まる距離による収束とする。
それはそう。普通は「位相」という言葉を使うけど、面倒なので……。
定義:無限和\sum_{i=1}^{\infty}a_iは、数列A_n=\sum_{i=1}^{n}a_iが収束するとき、その収束先を値として定義する。
要するに、\sum_{i=1}^{\infty}\frac{1}{2^i}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldotsというやつは、部分和のなす列(\frac{1}{2},\frac{3}{4},\frac{7}{8},\ldots)が1に収束するので\sum_{i=1}^{\infty}\frac{1}{2^i}=1というようにここを等号で結んじゃいますねという話です。これもFPSとか関係なく、無限和の定義に関するお話。
主張:体係数FPS環は完備離散付値環である。
証明:忘れた。代数学の本を読みましょう。
この"完備"というのは、付値によって定まる距離による距離空間としてみたとき完備であるという意味。距離空間が完備であるというのは、任意のコーシー列が収束するという意味。数列(a_n)がコーシー列であるとは、\forall \epsilon>0 \exists N \forall n,m\geq N. d(a_n,a_m)<\epsilon を満たすということ。収束列⇒コーシー列は一般に成り立つので、逆が成り立てば完備ということ。
例えば、有理数は完備ではない。なぜなら、列(3,3.1,3.14,3.141,3.1415,\ldots)はコーシー列だが、収束先が有理数の中に存在しないので。

exp再び

主張:有理数を含む体を係数とするFPS環において定義された\exp(f)は、fの定数項が0のとき、かつそのときに限り定義される。
証明:
・定数項が0⇒定義される
\exp_n(f)=\sum_{i=0}^{n-1}\frac{1}{i!}f^iとする。ここで、列F_n=\exp_n(f)を考える。少し考えると、n,m\geq N のとき、F_nF_mのN次未満の項は一致していることがわかる。つまり、数列(F_n)はコーシー列である。したがって完備性からこの数列は収束し、無限和の定義から収束先が\exp(f)である。
・定数項が0でない⇒定義されない
fの定数項をa_0\neq 0とする。A_n=\exp_n(a_0)を考えると、a_0は冪零でないので任意のnでA_n\neq A_{n+1}となる。したがって、列F_n=\exp_n(f)は任意のnでd(F_n,F_{n+1})=1となり、コーシー列でないので、特に収束列でない。

係数環が一般の環のときは、Mをa_0^M=0を満たす正整数として、証明中の「F_nF_mのN次未満の項は一致していることがわかる」を、「F_nF_mのN+1-M次未満の項は一致していることがわかる」に書き換えると定数項が冪零のケースがいえる。

つまり?

\mathbb{R}[[X]]の世界では\exp(1)=eとはしないよというのは、\exp_n(1)の列(1,2,5/2,8/3,\ldots)の定数項がいつまで経っても収束しないからですね。実数でいうところの、上の方の桁がいつまでもガチャガチャ変わってたら収束とはいわねえよという気持ちです(←これはかなり嘘が入っています。プロ各位怒らないで)

ここまでで7500文字くらいらしいです。一通りのトピックは書いたと思うし飽きたのでそろそろやめます

追記

Q.「expは\mathbb{Q}を含む環を係数とするFPS環上で定義される」って書いてるけど、mod998244353でやっとるやんけ、なんやねんぽまえ
A.完全に正しい指摘。でもn次未満の項しか必要ない場合、つまりR[[X]]/(X^n)で考えているときは、\expの代わりに\exp_nを使っても出てくるものは同じになるから、1,2,…,n-1さえ可逆なら十分なんですね~。
正確には、R[[X]]でexpが定義可能なとき以下の図が可換図式であり、右行ってから下行くルートは1,2,…,n-1さえ可逆なら定義できるので、「expが定義不可能だが、1,2,…,n-1が可逆」というときはこっちルートを採用して使いましょう、という意味。

 \require{AMScd}
  \begin{CD}
     R[[X]] @>自然な射影>> R[[X]] / (X^n)\\
     @V{\exp}VV @V{\exp_n}VV     \\
     R[[X]] @>自然な射影>> R[[X]] / (X^n)
  \end{CD}
正当性をいうには、以下が可換であることを言う必要があると思う。(右上から右下への写像がもし\exp_mなら自明だけど、実際には\exp_nなので、可換になることはby definitionとはいかないはず……)

 \require{AMScd}
  \begin{CD}
     R[[X]] /(X^m)@>自然な射影>> R[[X]] / (X^n)\\
     @V{\exp_m}VV @V{\exp_n}VV     \\
     R[[X]]  /(X^m)@>自然な射影>> R[[X]] / (X^n)
  \end{CD}


Q.logは?
A.expの逆演算として定めるよりは、天下りに定義したあと、expの逆演算になっていることを確かめる方が簡単でしょう。
定義:FPS環の元であって、定数項が1であるようなfに対して、\log(f)=\sum_{i\geq 1}\frac{(-1)^{i+1}}{i}(f-1)^i とする。
\exp(\log(f))=\log(\exp(f))=fとなることを各自確かめること

Q.指数法則とかchain ruleとか……
A.実は成り立ちます。でも、あなたのよく知るそれは、たぶん実関数の話ですよね。FPS環上の演算としてみても成立するかどうかは各自確かめること

期待値

期待値=((I-P)^{-1} \textbf{1})_0
というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。


問題:
S+1の状態があり、状態0から始めて、状態Sに到達したら終了。
1回の操作で状態iから状態jに遷移する確率がP_{i,j}のとき、終了するまでの操作回数の期待値は?

前置き:
グラフがDAG→DPしろ


本題に入る前に典型問題を一つ
問題:
裏が出るまでコイントスする。期待値何回?
答え:
n回目のコイントスをする確率が(1/2)^nだから、\sum_{n=0}^{\infty}(\frac{1}{2})^n=2

元の問題に戻る
P_{i,j}のi,j≠Sを並べてできる行列S×S行列をPとすると求める期待値は
\sum_{n=1}^{\infty}\text{$n$回目の操作を行う確率}\\
=\sum_{n=1}^{\infty}\text{$n-1$回目の操作後に状態$S$に到達しない確率}\\
=\sum_{n=0}^{\infty}\text{$n$回の操作で状態$S$に到達しない確率}\\
=\sum_{n=0}^{\infty}\sum_{v\neq S}\text{$n$回目の操作後に状態$v$である確率}\\
=\sum_{n=0}^{\infty}\sum_{v}P^n\text{の$(0,v)$成分}\\
=\sum_{v}\sum_{n=0}^{\infty}P^n\text{の$(0,v)$成分}\\
=\sum_{v}(\sum_{n=0}^{\infty}P^n)\text{の$(0,v)$成分}\\
=\sum_{v}(I-P)^{-1}\text{の$(0,v)$成分}
求まった。


問題2:
S+1の状態があり、状態0から始めて、状態Sに到達したら終了。
1回の操作で状態iから状態jに遷移する確率がP_{i,j}であり、このときコストC_{i,j}がかかる。終了するまでのコスト期待値は?

P_{i,j}のi,j≠Sを並べてできる行列S×S行列をP、i≠S並べてできるS×(S+1)行列をQとすると求める期待値は

\sum_{n=1}^{\infty}\sum_{(u,v)}\text{$n$回目の操作で状態$u$から$v$に遷移する確率}\times C_{u,v}\\
=\sum_{n=1}^{\infty}\sum_{(u,v)} P^{n-1} \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{n=0}^{\infty}\sum_{(u,v)} P^n \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}\sum_{n=0}^{\infty} P^n \text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(\sum_{n=0}^{\infty} P^n )\text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(I-P)^{-1}\text{の$(0,u)$成分} \times Q_{u,v}\times C_{u,v}\\
=\sum_{(u,v)}(I-P)^{-1}\text{の$(0,u)$成分} \times (Q\circ C)_{u,v}\\
=\sum_{v}\sum_{u}(I-P)^{-1}\text{の$(0,u)$成分} \times (Q\circ C)_{u,v}\\
=\sum_{v}(I-P)^{-1}(Q\circ C)\text{の$(0,v)$成分}
求まった。ここで\circアダマール積(element-wise product)を表す。

約数包除原理

\displaystyle{
\sum_{\substack{(x,y)\in S \\ \gcd(x,y)=1}}f(x,y)=\sum_d \mu(d)\sum_{\substack{(x,y)\in S \\ d\mid\gcd(x,y)}}f(x,y)}
というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。

記号
\mathbb{N}:=\{1,2,\ldots\}
[N]:=\{x\in \mathbb{N} \mid x\leq N\}
\mu:\mathbb{N}\to\mathbb{R} メビウス関数
命題Pに対して[P]をPが真なら1、偽なら0とする(アイバーソンの記法 - Wikipedia


やりたいこと
f:\mathbb{N}^2\to \mathbb{R}がある。\displaystyle F(N):=\sum_{\substack{(x,y)\in [N]^2 \\ \gcd(x,y)=1}}f(x,y)を求める。
例えばf=1 のときは実質totient sum


■ O(N) 約数包除
主張
fが次の3条件を満たすとき、F(N)はO(N)で計算できる。

  • あるh:\mathbb{N}\to\mathbb{R}が存在して任意の(d,x,y)でf(dx,dy)=h(d)f(x,y)が成り立つ。
  • 任意のnでh(n)がO(1)で計算できる
  • \displaystyle G(n):=\sum_{\substack{(x,y)\in [n]^2}}f(x,y)(gcdの条件がない)について、G\left(\left\lfloor\frac{N}{d}\right\rfloor\right) の列挙がO(N)

証明
実は\sum_{d|x}\mu(d)=[x=1]が成り立つ。メビウス関数はディリクレ積の意味でゼータ関数の逆元なのでそれはそう。
\displaystyle{
F(N)=\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=1}}f(x,y)\\
=\sum_{(x,y)\in[N]^2}f(x,y)[\gcd(x,y)=1]\\
=\sum_{(x,y)\in[N]^2}f(x,y)\sum_{d\mid\gcd(x,y)}\mu(d)\\
=\sum_{(x,y)\in[N]^2}\sum_{d\mid\gcd(x,y)}f(x,y)\mu(d)\\
=\sum_{1\leq d \leq N}\sum_{\substack{(x,y)\in[N]^2 \\d\mid\gcd(x,y) }}f(x,y)\mu(d)\\
=\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N]^2 \\d\mid\gcd(x,y) }}f(x,y)\\
=\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N/d]^2}}f(dx,dy)\\
=\sum_{1\leq d \leq N}\mu(d)\sum_{\substack{(x,y)\in[N/d]^2}}h(d)f(x,y)\\
=\sum_{1\leq d \leq N}\mu(d)h(d)\sum_{\substack{(x,y)\in[N/d]^2}}f(x,y)\\
=\sum_{1\leq d \leq N}\mu(d)h(d)G\left(\left\lfloor\frac{N}{d}\right\rfloor\right)
}
示せた。*1
\mu(d)h(d)区間\sum_{\left\lfloor\frac{N}{d}\right\rfloor=x}\mu(d)h(d)の列挙を前計算しておくと、GがO(1)で計算できるなら商をまとめるテクを使って本計算はO(N^{0.5})になる。
前計算は2/3乗とかでやることが多い[要出典]


■ O(N) 約数除
こっちのほうが計算量よくなるパターンが一生覚えられないんだよね

主張
fが次の3条件を満たすとき、F(N)はO(N)で計算できる。

  • あるh:\mathbb{N}\to\mathbb{R}が存在して任意の(d,x,y)でf(dx,dy)=h(d)f(x,y)が成り立つ。
  • 任意のnでh(n)がO(1)で計算できる
  • \displaystyle G(n):=\sum_{\substack{(x,y)\in [n]^2}}f(x,y)(gcdの条件がない)について、G\left(\left\lfloor\frac{N}{d}\right\rfloor\right) の列挙がO(N)

証明
\displaystyle{
F(N)=\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=1}}f(x,y)\\
=G(N)-\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)> 1}}f(x,y)\\
=G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N]^2 \\ \gcd(x,y)=d}}f(x,y)\\
=G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}f(dx,dy)\\
=G(N)-\sum_{2\leq d \leq N}\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}h(d)f(x,y)\\
=G(N)-\sum_{2\leq d \leq N}h(d)\sum_{\substack{(x,y)\in[N/d]^2 \\ \gcd(x,y)=1}}f(x,y)\\
=G(N)-\sum_{2\leq d \leq N}h(d)F\left(\left\lfloor\frac{N}{d}\right\rfloor\right)
}

O(N)かけて予めh(d)の累積和を前計算しておき、区間\sum_{\left\lfloor\frac{N}{d}\right\rfloor=x}h(d)をO(1)で取得できるようにしておくとGの計算量次第で本計算部分はO(N^{3/4})になる。
前計算がO(N^0.75)で済むなら、全体でもO(N^0.75)になる。

*1:演習問題:logついてませんか?

yukicoder 1962の解説の解説

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。

FPSパワーを感じる学びがあったのでまとめる。出典

「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は \displaystyle f_i(x):=\sum_{jはiの倍数でない}x^j になる。
したがって、「全ての要素が等しく、条件を満たすような長さ N の数列の個数」の母関数は g(x):=\sum_{i} f_i(x) であり、もとの条件を満たすような数列は、このような形の数列を任意個連結したものとして表すことができるので(?)、個数の母関数は \sum_k g(x)^k=\frac{1}{1-g(x)} となる……?
……というのは嘘。これだと例えば (2,2,2)(2,2,2) を連結して (2,2,2,2,2,2) が作れてしまう。

こういうことが起きる原因は、「全ての要素が i であり、条件を満たすような長さNの数列」のなす集合が連結で閉じていないせい。なので閉じるようにしよう(!)

一般に、あるオブジェクトであって重みNのものの個数の母関数が f であるとき、 \sum_{k\geq 1}f^k=\frac{f}{1-f} は、「オブジェクトを1個以上並べた列であって、重みの和がNになるものの個数」の母関数になる。この概念を悪用する。
あるオブジェクトであって重みNのものの個数の母関数が f であるとき、f=\frac{F}{1-F} を満たす F は「"それ"を1個以上並べることでオブジェクトを生成する何か」であって重みNのものの個数の母関数になる(???)
よって、fのかわりにFで考えることで任意個の連結について閉じるので、あとは前半で述べたのと同じようにして問題が解けた。

正当性はいい感じにやると示せるらしいけど(参考)、もとのオブジェクトを形式的に謎の概念に分解するという考え方はヤバさがあって好き。

ということで、「連続しない」という条件をFPSで形式的に処理することができるようになった。すげー

練習のためにいくつか問題を解いてみよう

類題
1以上M以下の整数からなる数列であって、同じ値が連続せず、和がNになるようなものはいくつあるか?
例:(N,M)=(4,3)のとき、(1,2,1),(1,3),(3,1)の3通り

「全ての要素がiであり、和がNであるような数列の個数」の母関数はf_i(x)=x^iで、これを同じものが連続しないように並べたいので、さっきと同じ問題になり、F_i=\frac{f_i}{1+f_i}G=\sum_i F_iとして、\frac{1}{1-G}が母関数

M=3の母関数 w|a


類題2
1以上M以下の整数からなる数列であって、mod Pが等しい値が連続せず、長さがNの数列はいくつ?
例:(N,M,P)=(3,4,3)のとき、(1or4,2,1or3or4),(1or4,3,1or2or4),(2or3,1or4,2or3),(2,3,1or2or4),(3,2,1or3or4)の26通り

1以上M以下の整数であってmod Pでiになるものの個数をC_iとする。「全ての要素がmod Pでiであり、長さがNであるような数列の個数」の母関数はf_i(x)=C_i x で、これを同じものが連続しないように並べたいので、F_i=\frac{f_i}{1+f_i}G=\sum_i F_iとして、\frac{1}{1-G}が母関数

(M,P)=(4,3)の母関数 w|a

ABC249Ex解説の解説

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。
オリジナル:Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)


数列 A に対して、終了条件を満たすまでの操作回数の期待値を E(A) とおく。
数列 A が1回の操作で数列 A' に変化する確率を P(A,A') とおく。
数列 A と整数 v に対して、f(A,v)=|\{i \mid A_i=v\}| とおく。
もし ある関数 E':\mathbb{N}\to\mathbb{R} と定数 C であって、
\sum_{v=1}^{N}E'(f(A,v))=E(A)+C
を満たすものが存在し、E',C を求めることができれば元の問題には答えられる。(f(A,v) を全ての v について求めるのは O(N) でできるので)

・そもそもそんな E' は存在するのか
E' が満たすべき必要十分条件を考える。
E は定義から、関数等式 E(A)=1+\sum_{A'} P(A,A')E(A') を満たす。
逆にこの性質を持つ関数 g であって、終了条件を満たす全ての Ag(A)=0 を満たすならば g=E である。
この関数等式に E',fE の関係式★をぶち込むと
\begin{eqnarray*}
  -C+\sum_{v=1}^{N}E'(f(A,v))&=&E(A)\\
&=&1+\sum_{A'} P(A,A')E(A')\\
&=&1+\sum_{A'} P(A,A')(-C+\sum_{v=1}^{N}E'(f(A',v)))
\end{eqnarray*}
となり、整理することで
① 任意の A\sum_{v=1}^{N}E'(f(A,v))=1+\sum_{A'} P(A,A')\sum_{v=1}^{N}E'(f(A',v))
という、E' が満たすべき関数等式を得る。さらに境界条件A が終了条件を満たすならば g(A)=0」から、CC=E'(N)+(N-1)E'(0) を満たすよう取れば良い。
よって①を満たすことが必要十分。
この条件をさらに厳しくし、
①' 任意の A,vE'(f(A,v))=\frac{1}{N}+\sum_{A'} P(A,A')E'(f(A',v))
を満たすものについて考えることにする。

ここで、\sum_{A'} P(A,A')E'(f(A',v))\sum_{y}E'(y)\sum_{f(A',v)=y} P(A,A') と書き換える。
\sum_{f(A',v)=y} P(A,A')、すなわち「A に対して1回操作を行った数列を A'とするとき、f(A',v)=y となる確率」は、操作を具体的に考察することで(←adhocポイント) f(A,v) のみに依存していることがわかるため、Q(f(A,v),y) と書ける。したがって①'は
①'' 任意の xE'(x)=\frac{1}{N}+\sum_{y}E'(y)Q(x,y)
に置き換えられる。両辺 N 倍することで、E' は明らかに、ある吸収マルコフ連鎖における各状態から終端状態に到るまでのステップ数の期待値を表す関数として実現可能であることがわかる。以上により存在が示せた。

E' を計算できるか
実際にE' を吸収マルコフ連鎖の期待値の関数だと思って計算したい気持ちになるので、やってみる。
全ての Q(x,y) がわかっているとする。
遷移行列をごちゃごちゃ計算すると O(N^3) で解けるがそれでは間に合わない。
操作を具体的に考察することで(←adhocポイント)、k>1 のとき Q(x,x+k)=0 となることがわかるので、遷移行列はほぼ三角行列になっている。
①''をぐっと睨むと E' に定数足したものも E' が満たすべき関数等式①''を満たすので、E'(0)の値を適当に決め打ちしてから、小さい方から順に求めていくことで O(N^2) で求められることがわかる。

Q を計算できるか
できます。頑張れ