ABC 429 G — Sum of Pow of Mod of Linear

考察

指数を時刻順に追うと、大きな歩幅のため剰余が頻繁に折り返すことがある。そこで、少し離れた時刻をたどることで値の変化が小さくなる組を探す。その時刻差ごとに列を分ければ、折返しの少ない等差数列にまとめられる。各列では冪の和が等比数列の和になるため、全項を生成せずに計算できる。

求める和は ∑k=0N−1X(Ak+B) mod M(modR)\sum_{k=0}^{N-1}X^{(Ak+B)\bmod M}\pmod R である。NN は最大 10910^9 なので、各時刻の指数を一つずつ計算する方法では間に合わない。まず周期を取り除き、その後に残った指数をまとめる方法を考える。

gcd縮約で底と周期をそろえる

g=gcd⁡(A,M)g=\gcd(A,M) とし、A=ga, M=gm, B=gb+b0 (0≤b0<g)A=ga,\ M=gm,\ B=gb+b_0\ (0\le b_0<g) と書く。元の指数は必ず b0b_0 と同じ余りを持ち、次のように表せる。

(Ak+B) mod M=b0+g((ak+b) mod m)(Ak+B)\bmod M=b_0+g\bigl((ak+b)\bmod m\bigr)

よって、底を Y=Xg mod RY=X^g\bmod R、外に掛ける因子を C=Xb0 mod RC=X^{b_0}\bmod R とすれば、答えは C∑k=0N−1Y(ak+b) mod m(modR)C\sum_{k=0}^{N-1}Y^{(ak+b)\bmod m}\pmod R になる。指数の法は mm、答えの法は引き続き RR である。

m=1m=1 なら縮約後の指数はすべて0なので、答えは CN mod RCN\bmod R。これで A=0A=0 も扱える。以下は m>1m>1 とする。このとき gcd⁡(a,m)=1\gcd(a,m)=1 なので、連続する mm 時刻の剰余は 0,1,…,m−10,1,\ldots,m-1 を一度ずつ取る。

N=qm+n (0≤n<m)N=qm+n\ (0\le n<m) と分けると、各完全周回の後は同じ剰余から再開するため、

答え=C(q∑v=0m−1Yv+∑k=0n−1Y(ak+b) mod m)(modR)\text{答え}=C\left(q\sum_{v=0}^{m-1}Y^v+\sum_{k=0}^{n-1}Y^{(ak+b)\bmod m}\right)\pmod R

となる。例えば (M,A,B,N)=(12,8,5,8)(M,A,B,N)=(12,8,5,8) では g=4, m=3, a=2, b=1, b0=1g=4,\ m=3,\ a=2,\ b=1,\ b_0=1。元の指数は (5,1,9,5,1,9,5,1)(5,1,9,5,1,9,5,1) であり、Y=X4, C=X, q=2, n=2Y=X^4,\ C=X,\ q=2,\ n=2 に対応する和は C{2(1+Y+Y2)+(Y+1)}C\{2(1+Y+Y^2)+(Y+1)\} である。完全周回の個数を元の MM で割って求めたり、底を元の XX のままにしたりしない。

以下は端数 nn 項の処理を考える。n=0n=0 なら端数和は0であり、分割自体が不要である。

小さい時刻差から小さい値の変化を作る

zk=(ak+b) mod mz_k=(ak+b)\bmod m と置く。まず、時刻順の列を折返しで切るだけでも等差数列にはなる。しかし歩幅が aa のままでは、本数が O(1+an/m)O(1+an/m) に達する。a,na,n が大きいと、ほとんど圧縮できない。

折返しを減らすには、進める歩幅を小さくしたい。隣の時刻にこだわらず、短い区間内で値が近い二点を探す。D=max⁡(2,⌈m⌉)D=\max(2,\lceil\sqrt m\rceil) とする。n≤Dn\le D なら各項を直接加算してよい。以下は n>Dn>D とする。

最初の DD 個の組 (zk,k) (0≤k<D)(z_k,k)\ (0\le k<D) を値順に並べ、その値を v0<v1<⋯<vD−1v_0<v_1<\cdots<v_{D-1} とする。D<mD<m かつ gcd⁡(a,m)=1\gcd(a,m)=1 より、値はすべて異なる。通常の隣接差は D−1D-1 個あり、総和は vD−1−v0≤m−1v_{D-1}-v_0\le m-1。したがって、その最小値 hh には

1≤h≤m−1D−11\le h\le\frac{m-1}{D-1}

が成り立つ。DD 点から通常の隣接差を取る場合、上界を m/Dm/D とはできない。例えば m=11,a=3,b=0,D=4m=11,a=3,b=0,D=4 の値は (0,3,6,9)(0,3,6,9) で、最小差3は 11/411/4 より大きい。個別公式解説にもこの定数境界があるため、ここでは上の隣接差の総和による論証で補正している。

最小差を与える二点を、今度は時刻順に i<ji<j と並べ、d=j−id=j-i とする。値順と時刻順は一致するとは限らないので、zj−zi=shz_j-z_i=sh となる符号 s∈{+1,−1}s\in\{+1,-1\} も保存する。すると

1≤d≤D−1,ad≡sh(modm)1\le d\le D-1,\qquad ad\equiv sh\pmod m

となる。これが、短い時刻差 dd ごとに進むと、値は小さな歩幅 +h+h または −h-h で動くという意味である。

時刻を分け、折返し直前までを一度に取る

時刻を k mod dk\bmod d ごとに分ける。余り r (0≤r<d)r\ (0\le r<d) の列は

k=r,r+d,r+2d,…,Lr=1+⌊n−1−rd⌋k=r,r+d,r+2d,\ldots,\qquad L_r=1+\left\lfloor\frac{n-1-r}{d}\right\rfloor

の LrL_r 項を持つ。先頭の値は y=(ar+b) mod my=(ar+b)\bmod m で、値の列は (y+shj) mod m (0≤j<Lr)(y+shj)\bmod m\ (0\le j<L_r) になる。すべての時刻は余りと列内の位置を一意に持つので、この分け方には漏れも重複もない。

例えば m=11,a=7,b=1,n=10m=11,a=7,b=1,n=10 では D=4D=4。最初の値は時刻順に (1,8,4,0)(1,8,4,0)、値順に (0,3),(1,0),(4,2),(8,1)(0,3),(1,0),(4,2),(8,1) という「値・時刻」の組になる。最小差は1で、対応する時刻を 0<30<3 と並べ直すと値は 1→01\to0 と減る。従って d=3,h=1,s=−1d=3,h=1,s=-1 である。

時刻の余り rr元の時刻 kk剰余の列折返しで切った列
00, 3, 6, 91, 0, 10, 9(1, 0), (10, 9)
11, 4, 78, 7, 6(8, 7, 6)
22, 5, 84, 3, 2(4, 3, 2)

各列を一項ずつ進める必要はない。現在値を yy、残りの項数を LL とすると、次の折返しの直前までに取れる項数 ℓ\ell は整数除算で求まる。

ℓ={min⁡(L,⌊m−1−yh⌋+1)(s=+1),min⁡(L,⌊yh⌋+1)(s=−1).\ell= \begin{cases} \min\left(L,\left\lfloor\dfrac{m-1-y}{h}\right\rfloor+1\right)&(s=+1),\\ \min\left(L,\left\lfloor\dfrac{y}{h}\right\rfloor+1\right)&(s=-1). \end{cases}

増加方向では y+h(ℓ−1)≤m−1y+h(\ell-1)\le m-1、減少方向では y−h(ℓ−1)≥0y-h(\ell-1)\ge0 を満たす最大の項数である。上の r=0r=0 の列では、最初は y=1,L=4y=1,L=4 なので ℓ=2\ell=2、すなわち (1,0)(1,0) を取る。次は y=(1−2) mod 11=10,L=2y=(1-2)\bmod11=10,L=2 となり、残りの (10,9)(10,9) を取る。

この ℓ\ell 項の和を加算したら、残りを L←L−ℓL\leftarrow L-\ell とする。まだ残るなら y←(y+shℓ) mod my\leftarrow(y+sh\ell)\bmod m へ進め、同じ処理を繰り返す。ここで負の剰余も 0≤y<m0\le y<m に正規化する。

分割後の本数も確認する。長さ LrL_r の列が円周上で進む距離は h(Lr−1)h(L_r-1) であり、折返し回数は高々 1+h(Lr−1)/m1+h(L_r-1)/m。出発位置によっては最初の一回がすぐ起こるので、この定数1を落としてはならない。初期の dd 本も合わせた全体の本数は

∑r=0d−1(2+h(Lr−1)m)=2d+h(n−d)m=O(d+hnm)=O(m).\sum_{r=0}^{d-1}\left(2+\frac{h(L_r-1)}m\right) =2d+\frac{h(n-d)}m =O\left(d+\frac{hn}m\right) =O(\sqrt m).

最後は d<Dd<D、h≤(m−1)/(D−1)h\le(m-1)/(D-1)、n<mn<m を使った。短い区間から対を探す負担と、折返しを処理する負担が、この DD の選び方で釣り合う。

負方向も、小さい指数からの等比数列として足す

折返しを含まない一片は y,y+sh,…,y+sh(ℓ−1)y,y+sh,\ldots,y+sh(\ell-1) である。s=−1s=-1 のまま底を Y−hY^{-h} とすると、YY の逆元が存在しない場合に困る。しかし和では項の順を変えてよいので、減少列だけ逆順に読む。

小さい方の指数を u=yu=y(増加方向)、u=y−h(ℓ−1)u=y-h(\ell-1)(減少方向)とすれば、どちらの寄与も

Yu∑j=0ℓ−1(Yh)j(modR)Y^u\sum_{j=0}^{\ell-1}(Y^h)^j\pmod R

である。例えば (10,9)(10,9) の寄与は Y9(1+Y)Y^9(1+Y)。負の指数も逆元も不要になる。

冪と和を組にして、除算せずに二分累乗する

比を ZZ とし、G(Z,t)=∑j=0t−1Zj(modR)G(Z,t)=\sum_{j=0}^{t-1}Z^j\pmod R と置く。G(Z,0)=0G(Z,0)=0 とする。等比数列の公式で Z−1Z-1 を割る方法は、RR が合成数だと使えるとは限らない。例えば Z=3,R=8Z=3,R=8 では Z−1=2Z-1=2 に逆元がない。Z=1Z=1 の場合も同じ実装で処理したい。

長さ tt の区間を (Pt,St)=(Zt,G(Z,t))(P_t,S_t)=(Z^t,G(Z,t)) で表す。長さ uu と vv の区間をつなぐと、後半の和には ZuZ^u を掛けるので、

(Pu,Su)∘(Pv,Sv)=(PuPv, Su+PuSv)(modR)(P_u,S_u)\circ(P_v,S_v) =(P_uP_v,\ S_u+P_uS_v)\pmod R

となる。空区間は (1,0)(1,0)、長さ1は (Z,1)(Z,1)。長さ1の組を二分累乗すれば、長さ tt の組を O(log⁡(t+1))O(\log(t+1)) 時間で求められる。例えば t=2t=2 は (Z2,1+Z)(Z^2,1+Z)、t=3t=3 は (Z3,1+Z+Z2)(Z^3,1+Z+Z^2) である。反復で実装すれば補助領域も定数で済む。

これで完全周回分は qG(Y,m)qG(Y,m)、各片の寄与は YuG(Yh,ℓ)Y^uG(Y^h,\ell) として求まる。YhY^h は全片で共通なので一度だけ計算し、端数和をすべて足した後、完全周回分との和に CC を掛ければ答えになる。n≤Dn\le D の場合は分割を省き、端数の各 YzkY^{z_k} を通常の二分累乗で足す。

典型の発動条件

Sqrt Heuristic for Floor Sums

線形剰余列で、元の歩幅による折返しが多すぎるときに候補となる。短い区間内の近接二点を値順に探し、時刻差で部分列に分ける。通常の隣接差から得る境界は d≤D−1,h≤(m−1)/(D−1)d\le D-1,h\le(m-1)/(D-1) であり、初期列も含めた本数 O(d+hn/m)O(d+hn/m) を評価して使う。

除算を使わない等比数列和

法が素数とは限らない、または比が1にもなるときは、冪と和を一組にして結合する。後半の和を前半の冪だけずらす操作は加算・乗算だけで閉じるため、逆元の有無によらず二分累乗できる。

問題固有の要素

今回、和の項は指数だけで決まり、時刻順を変えても答えが変わらない。この性質があるから、時刻差で列を分け、さらに減少列を逆順にしてもよい。順序に依存する集計へ転用する場合は、この並べ替えが許されるかを先に確認する。

正当性

gcd縮約の恒等式は元の各項を CYzkC Y^{z_k} に一致させる。互いに素な係数では周期内の剰余が全種類を一度ずつ取るため、完全周回を幾何和へ置き換えられる。端数の各時刻は k mod dk\bmod d と列内の位置で一意に表され、ad≡sh(modm)ad\equiv sh\pmod m より各列は符号付き歩幅 shsh で進む。整数除算で求めた項数は折返しを含まない最大の区間を切り出し、その直後から再開するので、全時刻を一度ずつ覆う。減少列の逆順化は和を保ち、冪と和の結合則は各片の幾何和を除算せず正しく計算する。従って、完全周回と全片の寄与を足して CC を掛けると元の和を得る。

実装上の注意

  • m=1m=1 は先に処理する。n=0n=0 なら端数和は0、n≤Dn\le D なら直接加算とし、DD 点の選択は n>Dn>D の場合だけ行う。
  • 値と元の時刻を組で保存する。値順の差 hh は正だが、時刻順の変化の符号 ss は別に必要である。
  • 区間長は「最後の添字」より1大きい。負方向では u=y−h(ℓ−1)u=y-h(\ell-1) としてから非負指数の累乗を使う。
  • XX は RR と互いに素とは限らず、縮約後の YY が0になることもある。二分累乗の初期値は常に1とし、指数0の項を保つ。
  • ak+bak+b、法 RR の下での積、完全周回数との積は32 bitに収まらない。制約内では符号付き64 bit整数を使える。JavaScriptの number では整数精度が足りないため bigint などを使う。負数の % は言語によって負になるので正規化する。

復習の核

  • 剰余を時刻順に追って折返しが多いなら、短い区間内で値が近い二点を探し、その時刻差で進んでみる。
  • 点が DD 個なら、通常の隣接差は D−1D-1 個。平方根本数の評価にも、最初からある dd 本と出発位置の影響を含める。
  • 和の順序を変えられるなら、負方向の等差指数列は逆順に読む。逆元を導入する前に、非負指数だけで表せないかを考える。
  • 等比数列和で割り算ができないときは、区間の「冪と和」を一緒に結合する。

計算量と制約

時間

縮約後の法を m=M/gcd⁡(A,M)m=M/\gcd(A,M) として、1ケースあたり O(mlog⁡(m+1)+log⁡(M+1))O(\sqrt m\log(m+1)+\log(M+1))。全体では O(TMlog⁡(M+1))O(T\sqrt M\log(M+1)) を上界とする。

最初の D=O(m)D=O(\sqrt m) 点の生成・ソートは O(mlog⁡(m+1))O(\sqrt m\log(m+1))。片は O(m)O(\sqrt m) 本で、各片の開始指数の累乗と幾何和はそれぞれ O(log⁡(m+1))O(\log(m+1))。直接加算する場合も高々 DD 項で同じ上界になる。gcd縮約と C,YC,Y の計算に O(log⁡(M+1))O(\log(M+1))、完全周回の幾何和に O(log⁡(m+1))O(\log(m+1)) を要する。周回数 qq は和に掛けるだけなので、log⁡N\log N の因子は付かない。

空間

O(m)O(\sqrt m)。最初の DD 個の値と時刻を保存し、各片は列挙した順に集計する。二分累乗は反復で行う。

制約との対応

1≤T≤1001\le T\le100、1≤N,M,R≤1091\le N,M,R\le10^9、0≤A,B<M0\le A,B<M、1≤X<R1\le X<R。M≤109M\le10^9 なので D≤31623D\le31623 であり、指数を最大 10910^9 項生成する代わりに平方根本数の片を扱う。RR の素数性や XX の可逆性は仮定しない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sum of Pow of Mod of Linear の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 整数境界と同値区間を正確に分ける

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

    主タグ: 整数境界・同値区間分割

    補助タグ: 線形遷移・行列累乗

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

    学習の位置

    体系上の位置: 整数境界と同値区間を正確に分ける

    • 圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。

    先に読む単元:

    この解説で扱わないこと:

    • 素因数指数による整数条件の分解。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題