ABC 270 G — Sequence in mod P

考察

目標から一歩ずつ逆にたどった状態を表にし、出発点から大きな幅で進んだ状態との一致を探す。逆に戻れることと、何歩分もの遷移を一つの式にまとめられることが、この問題で長い数列を走査せずに済む理由になる。

先に直接答えられる場合を分ける

求めるのは、初項 X0=SX_0=S、遷移 Xt+1=(AXt+B) mod PX_{t+1}=(AX_t+B)\bmod P に対して、Xt=GX_t=G となる最小の非負整数 tt である。まず S=GS=G なら、他の条件によらず答えは0になる。

以後は S≠GS\ne G とする。A=0A=0 なら一歩後からずっと BB なので、G=BG=B なら1、そうでなければ到達不能の −1-1 を返す。逆写像を作るのは残りの A≠0A\ne0 の場合だけでよい。

逆に戻れるなら、時刻を二つに分けられる

ここから合同式はすべて法 PP で考える。PP は素数で A≠0A\ne0 なので、AA の逆元 A−1A^{-1} が存在する。f(x)=Ax+Bf(x)=Ax+B と置き、y=f(x)y=f(x) を xx について解くと、

y=Ax+B⟺x=A−1(y−B)y=Ax+B\quad\Longleftrightarrow\quad x=A^{-1}(y-B)

となる。従って f−1(y)=A−1(y−B)f^{-1}(y)=A^{-1}(y-B) が逆写像であり、各状態の直前の状態は一意に決まる。逆元は AP−2 mod PA^{P-2}\bmod P を高速累乗で一度計算すればよい。

可逆な遷移を有限個の状態上で繰り返すと、出発点から周期をなす。状態は PP 個なので、目標へ到達するなら最初の時刻は PP 未満である。ただし、一歩ずつ調べると一ケースで最大 10910^9 回程度の遷移が必要になる。

そこで探索幅を W=⌈P⌉W=\lceil\sqrt P\rceil とし、時刻を商と余りに分ける。fkf^k は ff の kk 回の適用を表し、f0f^0 は何も変えない写像とする。

t=iW+j,0≤j<W,0≤iW+j<Pt=iW+j,\qquad 0\leq j<W,\quad 0\leq iW+j<P

到達条件の両辺に逆写像を jj 回適用すると、

fiW+j(S)=G⟺fiW(S)=f−j(G)f^{iW+j}(S)=G\quad\Longleftrightarrow\quad f^{iW}(S)=f^{-j}(G)

となる。左辺は出発点から WW 歩ずつ、右辺は目標から逆向きに一歩ずつ進めた状態である。右辺を表にしておけば、各 ii について WW 通りの jj を毎回試す必要がなくなる。

一giant stepを一次式の評価にまとめる

WW 歩進むたびに ff を WW 回適用しては、全体が再び O(P)O(P) 時間になる。ここでは fWf^W も一次式になることを使う。

一次式の写像 x↦ax+bx\mapsto ax+b を係数の組 (a,b)(a,b) で表す。(c,d)(c,d) を適用した後に (a,b)(a,b) を適用するなら、代入して

a(cx+d)+b=(ac)x+(ad+b)a(cx+d)+b=(ac)x+(ad+b)

を得るので、合成後の係数は (ac,ad+b)(ac,ad+b) である。定数項が ad+bad+b になるのは、先に足した dd にも後の係数 aa が掛かるためだ。順序を逆にした合成とは区別する。

単位写像 (1,0)(1,0) を初期値とし、(A,B)(A,B) をこの合成で二分累乗すると、O(log⁡W)O(\log W) 回の合成で fW(x)=αx+βf^W(x)=\alpha x+\beta を求められる。あるいは、(a,b)=(1,0)(a,b)=(1,0) から (a,b)←(Aa,Ab+B)(a,b)\leftarrow(Aa,Ab+B) を WW 回同時更新しても、前計算は O(W)O(W) 時間に収まる。一度係数 α,β\alpha,\beta を得れば、各giant stepは x←(αx+β) mod Px\leftarrow(\alpha x+\beta)\bmod P の定数時間の更新になる。

二つの表現を照合する

一ケースの手順は次のとおり。二分累乗による前計算を使う。

  1. 前述の S=GS=G、A=0A=0 を処理する。残りで A−1A^{-1} と fWf^W の係数を前計算する。
  2. y=Gy=G から始め、j=0,1,…,W−1j=0,1,\ldots,W-1 の順に状態 yy と添字 jj を表へ保存し、y←A−1(y−B) mod Py\leftarrow A^{-1}(y-B)\bmod P と更新する。同じ状態が登録済みなら上書きせず、最小の jj を残す。
  3. x=Sx=S から始め、i=0,1,…,⌊(P−1)/W⌋i=0,1,\ldots,\lfloor(P-1)/W\rfloor の順に表で xx を探す。一致した添字を jj として、iW+j<PiW+j<P ならその時刻を返す。次の状態は x←(αx+β) mod Px\leftarrow(\alpha x+\beta)\bmod P で得る。
  4. 最後まで範囲内の一致がなければ −1-1 を返す。

公式入力例の最初のケース、P=5,A=2,B=1,S=1,G=0P=5,A=2,B=1,S=1,G=0 を追う。W=3W=3 で、2−1=3(mod5)2^{-1}=3\pmod5 だから逆写像は 3(y−1)3(y-1)。baby側の表は次のようになる。

添字 jj012
目標から逆に戻った状態 f−j(0)f^{-j}(0)023

順向きには f2(x)=4x+3f^2(x)=4x+3、f3(x)=8x+7≡3x+2(mod5)f^3(x)=8x+7\equiv3x+2\pmod5 なので、giant側は1から始まり、次が 3⋅1+2≡03\cdot1+2\equiv0 となる。

添字 ii01
WW 歩ずつ進んだ状態 fiW(1)f^{iW}(1)10
一致する表の添字 jjなし0

最初の一致は i=1,j=0i=1,j=0 なので、答えは 1⋅3+0=31\cdot3+0=3。実際の列 1→3→2→01\to3\to2\to0 と一致する。

一方、短周期では表に重複ができる。P=11,A=10,B=0,S=1,G=10,W=4P=11,A=10,B=0,S=1,G=10,W=4 なら逆写像も 10y mod 1110y\bmod11 で、baby側は 10,1,10,110,1,10,1 となる。状態1に最小の j=1j=1 を残すと、giant側の初期状態1と照合して答え1を得る。最後の j=3j=3 で上書きすると、同じ最初の照合で3を返してしまう。従って、表の重複処理まで含めて最小時刻を保証する必要がある。

典型の発動条件

Baby-Step Giant-Step

可逆な遷移の反復で最初の到達時刻を求めたいが、一歩ずつの走査は長すぎるときに候補になる。必要なのは探索時刻の上限、逆向きの一歩、幅をまとめた順向きの一歩をそれぞれ求める方法である。

本問では目標側から逆向きに進む表と、出発点側から順向きに進む列を照合する。表の向きを決めてから一致条件を書き、候補時刻を復元する。

affine mapの合成と逆写像

遷移が一次式なら、合成しても係数二つで表せることに注目する。結合則を持つ合成を使って高速累乗すれば、多数回の反復を一つの写像へまとめられる。

逆写像には乗数の逆元が必要である。合成できることと逆に戻れることは別の条件なので、両方を確認する。

問題固有の要素

法が素数なので、A≠0A\ne0 だけで逆元の存在が保証される。A=0A=0 は逆に戻れないが、状態が一歩で一定になるため直接答えられる。可逆性が必要な解法では、使えないパラメーターを先に分類すると、かえって簡単な場合として処理できることがある。

A=1A=1 でもこの手順を使える。A−1A-1 で割る変形を使っていないため、追加の場合分けは不要である。

正当性

S=GS=G なら0が最小である。S≠G,A=0S\ne G,A=0 なら、時刻1以降は常に BB なので、G=BG=B のときだけ最小時刻1を返せばよい。

残りでは ff は全単射である。軌道で Xu=XvX_u=X_v(0≤u<v0\leq u<v)となったとき、逆写像を uu 回適用すれば S=Xv−uS=X_{v-u} となる。従って軌道は出発点から周期をなし、その長さは状態数 PP 以下である。到達する目標の最初の出現は必ず 0≤t<P0\leq t<P に含まれる。

範囲内の任意の時刻を t=iW+jt=iW+j、0≤j<W0\leq j<W と分けると、可逆性により ft(S)=Gf^t(S)=G と fiW(S)=f−j(G)f^{iW}(S)=f^{-j}(G) は同値である。よって照合から返す時刻では必ず目標に到達し、到達時刻があればその商に対応するgiant stepで一致が見つかる。重複をまとめても同じ状態の最小の jj は残るため、到達候補は失われない。

固定した ii では最小の jj が最も早い候補であり、ii を増やすと候補時刻の区間 [iW,(i+1)W)[iW,(i+1)W) が昇順に並ぶ。従って ii 昇順で最初に見つけた範囲内の一致が最小時刻になる。最終区間で保存した jj が iW+j≥PiW+j\geq P を満たすなら、同じ状態のより大きい添字もすべて範囲外である。最後まで一致がなければ、周期内に目標がなく到達不能である。

実装上の注意

  • S=GS=G を最初に判定する。A=0A=0 の場合も、S=G=BS=G=B の答えは1ではなく0である。
  • 表には最小の jj を残す。jj 昇順で初回だけ挿入すればよく、短周期でも上書きしない。
  • giant側は iW<PiW<P の間だけ調べ、候補にも iW+j<PiW+j<P を要求する。W=⌈P⌉W=\lceil\sqrt P\rceil は整数の二乗で確かめると丸め誤差を避けられる。
  • 引き算 y−By-B は負になり得るので、剰余を 0,…,P−10,\ldots,P-1 に正規化する。係数の合成では、更新前の係数から二つの新しい値を計算する。
  • 係数の積や αx+β\alpha x+\beta は 101810^{18} 程度になり得る。C++などでは符号付き64 bit整数で計算してから剰余を取り、32 bitで先に掛けない。

復習の核

  • 反復回数が大きいときは、時刻を商と余りに分け、逆向きに戻した目標と順向きに進めた出発点を照合できないか考える。
  • 逆に戻れるだけでは高速化にならない。大きな幅を一度で進める写像も前計算する。
  • 最小時刻を返すには、表の重複で残す添字と、giant側を調べる順序の両方が必要になる。

計算量と制約

時間

一ケースで逆元の高速累乗に O(log⁡P)O(\log P)、fWf^W の合成の二分累乗に O(log⁡W)O(\log W) 時間。baby側は WW 状態、giant側は高々 ⌈P/W⌉\lceil P/W\rceil 状態であり、一回の状態更新は定数時間である。

hash表なら、構築・照合を含めて期待 O(log⁡P+W+P/W)=O(P)O(\log P+W+P/W)=O(\sqrt P) 時間。平衡二分探索木などの順序付き辞書なら、各操作の最悪 O(log⁡W)O(\log W) を含めて最悪 O(Plog⁡P)O(\sqrt P\log P) 時間となる。全 TT ケースの時間は、各ケースの費用の総和である。

空間

表に保存する状態は高々 WW 個なので、一ケース O(P)O(\sqrt P)。二分累乗は係数二つの組を定数個使う反復実装でよい。ケースを順に処理して表を使い回せば、全ケース分の表を同時に持つ必要はない。

制約との対応

公式制約は 1≤T≤1001\leq T\leq100、素数 2≤P≤1092\leq P\leq10^9、0≤A,B,S,G<P0\leq A,B,S,G<P。実行時間制限は4秒、メモリ制限は1024 MiBである。最大の WW は31623で、各ケースで両方向をそれぞれ約3.2万状態に抑えられる。hash表なら十分な容量を確保し、辞書を使う場合はその操作費用も含めて実装する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sequence in mod P の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Baby-Step Giant-Step・可逆作用の反復到達探索

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: Baby-Step Giant-Step・可逆作用の反復到達探索

    補助タグ: 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: Baby-Step Giant-Step・可逆作用の反復到達探索

    • 有限群の累乗または可逆な有限orbitについて、反復到達時刻をbaby/giant幅へ分解し、逆向きbaby tableと前向きgiant sequenceの衝突からindexを復元できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題