ABC 387 G — Prime Circuit

考察

二つの閉路が触れ合うと、辺を使い直さずに偶数長の回路を作れる。そこでまず、許されるグラフを「互いに頂点を共有しない素数長の閉路を、橋でつないだ構造」として捉える。根を一つ選ぶと橋の先が独立な子構造へ分かれ、その数え上げを指数型母関数の方程式にできる。

回路の条件をグラフの形へ移す

この問題の回路は、辺を再使用しない非空の閉じた道であり、同じ頂点を複数回通ってよい。一方、単純閉路は始点と終点以外に頂点の重複を持たない閉じた道である。単純閉路も回路なので、その長さは素数でなければならない。グラフは単純だから長さ2の閉路はなく、許される長さは3以上の奇素数に限られる。

単純閉路だけを調べて終わることはできない。例えば、二つの三角形が一頂点だけを共有すると、片方を一周してからもう片方を一周する長さ6の回路ができる。また、二つの三角形が辺 uvuv を共有し、残りの頂点が a,ba,b なら、u→a→v→b→uu\to a\to v\to b\to u が長さ4の単純閉路になる。

一般の場合も、辺を共有しなければ二閉路をつなげて一周ずつ回り、辺を共有すれば内部頂点の交わらない三本の道の偶奇を比べることで矛盾を作れる。逆に、頂点を共有しない素数長閉路を橋でつないだグラフでは、回路は橋を使えないので、一つの閉路を一周するしかない。詳しい構成は「正当性」で示す。

橋を切り、根の属する部分から数える

nn 頂点のラベル付きグラフの答えを ana_n とする。各グラフでさらに一頂点を根に選ぶと nann a_n 通りなので、その指数型母関数を

F(x)=∑n≥1nann!xnF(x)=\sum_{n\geq1}\frac{n a_n}{n!}x^n

と定める。xx は頂点数を記録する変数で、空グラフを含めないため F(0)=0F(0)=0 である。

橋とは、取り除くとグラフが非連結になる辺である。すべての橋を切ると、各部分は単独頂点か一つの素数長閉路になる。各部分を縮約したグラフは木なので、根の属する部分から外向きに見れば、各橋の先を子構造として一意に切り出せる。

部分内の一頂点に注目する。その頂点から外へ出る橋の本数を kk とすると、各橋の先には、橋の端点を根とした FF の構造が一つ付く。子同士は頂点を共有せず、子を並べる順序もない。従って、ラベルを分配して順序のない集合を作る指数型母関数の規則から、この一頂点と橋の先をまとめた母関数は

U(x)=x∑k≥0F(x)kk!=xexp⁡F(x)U(x)=x\sum_{k\geq0}\frac{F(x)^k}{k!}=x\exp F(x)

となる。先頭の xx は部分内の頂点自身を数え、子の根はそれぞれの FF で既に数えている。橋は辺なので頂点数を増やさず、新たな xx を掛ける必要はない。

根の属する部分が単独頂点なら寄与は UU。長さ pp の閉路なら、各頂点を UU で置き換えた根付き閉路を数える。ここで、閉路を回転させた重複と、向きを反転させた重複を区別する。

固定した pp 個のラベルに対し、根の選択が pp 通り、根から出発して残りを並べる順序が (p−1)!(p-1)! 通りある。逆向きにたどった二つの列が同じ無向閉路を表すので、個数は p(p−1)!/2p(p-1)!/2。指数型母関数ではこれを p!p! で割るから、係数は 1/21/2 となる。根が開始点を定めているので、さらに巡回の pp で割らない。 例えば三頂点では、三角形は一つで根が三通りあり、係数は 3/3!=1/23/3!=1/2 である。

以上から、根の属する部分を表す級数を GG と置けば

G(x)=x+12∑p≥3p は素数xp,U(x)=xexp⁡F(x),F(x)=G(U(x)).\begin{aligned} G(x)&=x+\frac12\sum_{\substack{p\geq3\\p\text{ は素数}}}x^p,\\ U(x)&=x\exp F(x),\\ F(x)&=G(U(x)). \end{aligned}

を得る。例えば x4x^4 未満では G(x)=x+x3/2G(x)=x+x^3/2 なので、方程式を展開すると F(x)=x+x2+2x3(modx4)F(x)=x+x^2+2x^3\pmod{x^4} となる。従って a3=2!⋅2=4a_3=2!\cdot2=4 であり、三頂点の木三つと三角形一つを数えられる。

合成を高速化してNewton法で解く

グラフの辺集合を列挙すると候補は 2(N2)2^{\binom N2} 個ある。構造を母関数へ移せても、係数を逐次求める素朴な積や合成には二次時間以上かかり、N≤2.5×105N\leq2.5\times10^5 に届かない。ここでは FPS合成・power projection の高速合成を使い、暗黙方程式をNewton法で解く。

高速合成は、固定した内側の級数に対し、外側の係数から合成結果の係数への線形写像を計算する。転置側は、補助級数 hh と内側の級数 ff に対する [xn]f(x)ih(x)[x^n]f(x)^i h(x) の列を求める power projection であり、Bostan–Mori型の係数抽出へ帰着できる。その線形操作を逆順に転置したものが Kinoshita–Li 合成で、精度 mm の合成を O(mlog⁡2m)O(m\log^2m) 時間で行える。今回の内側 UU は定数項0なので、この合成の前提も満たす。

まず篩で NN 以下の素数を列挙し、GG を NN 次まで作る。次に F=0F=0、精度 d=1d=1、つまり定数項だけが正しい状態から始める。各段で目標精度を m=min⁡(2d,N+1)m=\min(2d,N+1) とし、既知の FF の高次を0で延長した上で、以下をすべて xmx^m 未満まで計算する。

U=xexp⁡F,R=G(U)−F,J=UG′(U)−1,F←F−RJ−1(modxm).\begin{aligned} U&=x\exp F,\\ R&=G(U)-F,\\ J&=U G'(U)-1,\\ F&\leftarrow F-RJ^{-1}\pmod{x^m}. \end{aligned}

ここで G′G' は GG の変数による微分である。JJ は G(xexp⁡F)−FG(x\exp F)-F の FF に関する微分なので、連鎖律による UU を忘れない。U(0)=0U(0)=0 より J(0)=−1J(0)=-1 であり、FPSの逆元 J−1J^{-1} が存在する。G(U)G(U) と G′(U)G'(U) を高速合成で評価し、更新後に d=md=m とする。誤差が二乗されるため精度を倍にでき、d=N+1d=N+1 まで繰り返せばよい。

最後に答えとして

aN=(N−1)! [xN]F(x)(mod998244353)a_N=(N-1)!\,[x^N]F(x)\pmod{998244353}

を返す。N!N! を掛けるだけでは、根の選択 NN 通りを余分に数える。N=1N=1 でも一次係数1に 0!=10!=1 を掛けて答え1になる。

別経路として、H(t)=exp⁡G(t)H(t)=\exp G(t) と置くと U=xH(U)U=xH(U)、すなわち U/H(U)=xU/H(U)=x になる。従って t/H(t)t/H(t) の合成逆関数から UU を求め、F=log⁡(U/x)F=\log(U/x) としてもよい。この経路も高速な合成逆関数を必要とする。

典型の発動条件

block decompositionと指数型母関数

連結なラベル付き構造で、根の属する部分を決めると残りが独立な子構造へ分かれるときに使う。今回の部分は単独頂点または素数長閉路であり、橋の先の子が順序のない集合になるため exp⁡F\exp F が現れる。まず分解と復元が一意かを確認する。

転置原理によるFPS composition

固定した内側の級数に対する合成は、外側の係数について線形である。その転置である power projection を有理関数の係数抽出として高速に処理できれば、合成も高速化できる。無限FPSを有限精度で合成する際は、内側の定数項0を確かめる。

FPS Newton iteration

暗黙方程式の低次係数が既知で、未知級数についての微分が可逆なとき、誤差を線形化して精度を倍にする。今回確認すべき値は J(0)=−1J(0)=-1 であり、各段の評価には高速合成とFPS基本演算を使う。

問題固有の要素

回路が頂点を再訪できることから、閉路の長さだけでなく、二つの閉路が接触したときに生まれる回路まで調べる必要がある。奇数長閉路が頂点を共有すると偶数長回路ができるため、一般のcactusより強い「閉路同士が頂点を共有しない」という制約になる。

この条件によって、根の属する閉路は高々一つに定まり、そこへ別の閉路を同じ頂点で貼り付けることはできない。子は必ず橋を介して付ける。この区別が、今回の母関数を立てる際の要点である。

正当性

まず、条件を満たすグラフの全単純閉路は素数長である。単純グラフの単純閉路は長さ3以上なので、その素数長は奇数になる。異なる二つの単純閉路が頂点を共有すると仮定し、辺を共有するかどうかで分ける。

辺を共有しない場合、共通頂点から一方を一周し、続けて他方を一周する。各辺を一度だけ使い、始点へ戻るので回路である。その長さは二つの奇数の和であり、6以上の偶数となって素数長条件に反する。

辺を共有する場合、一方を CC、他方を DD とする。異なる単純閉路なので、DD には CC に属さない辺がある。DD をたどり、CC の辺から外れてから次に CC の頂点へ戻る区間を一つ取る。この道の両端を u,vu,v とすれば、内部の頂点は CC に属さない。共有辺の両端を含めて DD は CC と二頂点以上で交わり、DD は単純なので u≠vu\ne v である。

この道と、CC 上の二つの uu–vv 間の弧を合わせると、内部頂点を共有しない三本の道になる。三本の長さのうち少なくとも二本は同じ偶奇である。一方を uu から vv へ、他方を vv から uu へたどれば、辺を再使用しない偶数長の単純閉路ができる。単純グラフなので長さ2にはならず、これも素数長条件に反する。従って、異なる単純閉路は頂点を共有しない。

逆に、全単純閉路が互いに頂点を共有せず、各長さが素数であるグラフを考える。どの単純閉路にも属さない辺は橋である。橋を渡ってから始点側へ戻るには同じ橋をもう一度使う必要があるため、回路は橋を使えない。橋を除いた各連結成分は単独頂点または一つの単純閉路であり、辺を再使用しない非空の閉じた道はその閉路一周に限られる。よって全回路が素数長となり、特徴付けは必要十分である。

橋をすべて切ると、根の属する部分は単独頂点または根付き素数長閉路として一意に定まる。各頂点から橋でつながる子側も、橋の端点を根とした同じ条件のグラフである。子側のラベル集合は互いに素で、順序を持たない集合として一意に復元できる。逆にこれらを橋で付ければ新たな閉路は生じない。根付き閉路のラベル上の個数は p(p−1)!/2=p!/2p(p-1)!/2=p!/2 なので、その指数型母関数の係数は 1/21/2。従って、この対応は U=xexp⁡FU=x\exp F、F=G(U)F=G(U) を漏れも重複もなく表す。

最後に、A(F)=G(xexp⁡F)−FA(F)=G(x\exp F)-F を考える。FF に xdx^d の倍数である補正 Δ\Delta を加えると、A(F+Δ)≡A(F)+JΔ(modx2d)A(F+\Delta)\equiv A(F)+J\Delta\pmod{x^{2d}} となる。J=UG′(U)−1J=UG'(U)-1 は定数項が −1-1 なので可逆であり、Δ=−A(F)/J\Delta=-A(F)/J によって精度が倍になる。定数項0から係数が一意に定まるため、Newton法は上の組合せ分解の母関数を求める。根を選ぶ倍率を除けば、答えは (N−1)! [xN]F(x)(N-1)!\,[x^N]F(x) である。

実装上の注意

  • 閉路の項は素数 p≥3p\geq3 だけを作り、係数には法 998244353998244353 上の 2−12^{-1} を使う。長さ2の閉路や、追加の 1/p1/p を入れない。
  • 目標は xN+1x^{N+1} 未満の精度である。各段の合成・指数・逆元・積をその段の精度へ切り詰め、微分した G′G' も必要次数まで渡す。
  • Newton法の補正は F−R/JF-R/J。J=UG′(U)−1J=UG'(U)-1 の UU と符号を保持する。高次を0で延長して計算した残差を使い、未知の係数を既知として扱わない。
  • 合成逆関数を使う別経路で F=log⁡(U/x)F=\log(U/x) を計算するなら、UU は N+1N+1 次まで必要になる。xx で割ると次数が一つ下がるため、Newton法で直接 FF を求める場合と必要精度が異なる。
  • 最後の係数には (N−1)!(N-1)! を掛ける。閉路を含まない木も、GG の一次項から既に数えている。

復習の核

  • 全回路への条件では、頂点を再訪して複数の閉路をつなげた回路も調べる。共有辺があれば、内部頂点の交わらない三本の道を探して偶奇を比べる。
  • exp⁡F\exp F を使う前に、子がどの辺で切り離され、どこを根とし、なぜ順序を持たないかを説明する。
  • 対称性で割る数は、根を付ける前後で変わる。今回の閉路は開始点が決まるので反転の2だけを割り、最後には根の選択倍率を除く。
  • Newton法は微分の定数項の可逆性と倍精度の不変量を確認する。反復の回数だけで計算量を評価せず、各精度の費用を足し合わせる。

計算量と制約

時間

O(Nlog⁡2N)O(N\log^2N)。篩は O(Nlog⁡log⁡N)O(N\log\log N)、階乗の準備は O(N)O(N)。精度 mm のNewton更新では定数回の高速合成が O(mlog⁡2m)O(m\log^2m)、指数・逆元・積が O(mlog⁡m)O(m\log m) である。精度を倍にする各段の費用の和は O(Nlog⁡2N)O(N\log^2N) に収まり、反復回数による余分な log⁡N\log N は掛からない。

空間

O(Nlog⁡N)O(N\log N)。合成の転置計算のために各段の作業表を保存する実装を用いる。各精度の計算領域を使い回せば、Newton法の全反復を通じてもこの範囲に収まる。素数表・階乗・級数の係数列は O(N)O(N)。

制約との対応

公式制約は 1≤N≤2.5×1051\leq N\leq2.5\times10^5、時間制限12秒、メモリ制限1024 MiBである。高速合成の O(Nlog⁡2N)O(N\log^2N) 時間・O(Nlog⁡N)O(N\log N) 空間を前提とし、素朴な合成やグラフ列挙には戻さない。答えの法 998244353998244353 は素数で、必要な階乗・積分の分母は法より小さく可逆である。FPSの指数・逆元と高速合成にはNTTによる畳み込みを用いる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Prime Circuit の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: FPS合成・power projection

主題
  • FPS合成・power projection: 多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
既習技能

主タグ: 形式的べき級数の基本演算 FPS合成・power projection 生成関数による組合せ構造の符号化

補助タグ: 畳み込み・相互相関

執筆: abc-explanation-author1.1.1 / revision 3

学習の位置

体系上の位置: FPS合成・power projection

  • 多項式/FPSのcompositionとその転置であるpower projectionを、block分割・transposition・rational functionへ還元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
  • 定数項の前提と次数打切りを確認し、Newton法を用いたFPSの逆数・対数・指数などを畳み込み計算へ還元できる。
  • 組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。

先に読む単元:

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題