ABC 438 G — Sum of Min

考察

同じ A の要素を使う項だけを集めると、相手の B の添字は一定の歩幅で進む。この「訪れる順」に B を並べ替えれば、巨大な項数を円環の全周回と短い区間に分けられる。まず二つの周期の共通因子を取り除き、一周ですべての位置を訪れる形にする。

求める和は、問題文と同じ0始まりの添字で

∑i=0K−1min⁡(Ai mod N,Bi mod M)\sum_{i=0}^{K-1}\min(A_{i\bmod N},B_{i\bmod M})

である。KK は最大 101810^{18} なので、各項の直接走査はできない。組の周期 lcm⁡(N,M)\operatorname{lcm}(N,M) も最大 NMNM に達するため、一周期をそのまま列挙する方針も避けたい。そこで、種類が NN 個しかない A の添字を固定し、その要素が出る時刻をまとめて扱う。

共通剰余ごとに局所時刻を作る

g=gcd⁡(N,M)g=\gcd(N,M)、N′=N/gN'=N/g、M′=M/gM'=M/g とおく。時刻を i=r+gti=r+gt(0≤r<g0\leq r<g)と一意に書くと、N=gN′N=gN'、M=gM′M=gM' より

i mod N=r+g(t mod N′),i mod M=r+g(t mod M′)\begin{aligned} i\bmod N&=r+g(t\bmod N'),\\ i\bmod M&=r+g(t\bmod M') \end{aligned}

となる。つまり、A と B で参照する添字の gg による剰余は常に同じで、異なる剰余同士の組は現れない。

剰余 rr の部分列を Aj(r)=Ar+gjA^{(r)}_j=A_{r+gj}(0≤j<N′0\leq j<N')、Bv(r)=Br+gvB^{(r)}_v=B_{r+gv}(0≤v<M′0\leq v<M')とする。このクラスの局所時刻 tt の個数は、r+gt<Kr+gt<K から

Kr=max⁡(0,1+⌊K−1−rg⌋)K_r=\max\left(0,1+\left\lfloor\frac{K-1-r}{g}\right\rfloor\right)

である。よって元の和を、各 rr についての

∑t=0Kr−1min⁡(At mod N′(r),Bt mod M′(r))\sum_{t=0}^{K_r-1}\min(A^{(r)}_{t\bmod N'},B^{(r)}_{t\bmod M'})

に分けられる。K<gK<g のときは r≥Kr\geq K のクラスが空になる。以降は一つの rr を固定する。縮約後は gcd⁡(N′,M′)=1\gcd(N',M')=1 である。

A を固定した訪問順を円環の連続位置へ移す

Aj(r)A^{(r)}_j を使う局所時刻は t=j+hN′t=j+hN' と表せる。その出現回数を cjc_j とすると、0≤t<Kr0\leq t<K_r より

cj=max⁡(0,1+⌊Kr−1−jN′⌋)c_j=\max\left(0,1+\left\lfloor\frac{K_r-1-j}{N'}\right\rfloor\right)

で、h=0,…,cj−1h=0,\ldots,c_j-1 が対応する。cj=0c_j=0 の要素は処理しなくてよい。相手の B の添字は (j+hN′) mod M′(j+hN')\bmod M' と進むので、訪れる順に並べた長さ M′M' の配列

Bu′=BN′u mod M′(r)(0≤u<M′)B'_u=B^{(r)}_{N'u\bmod M'}\qquad(0\leq u<M')

を作る。互いに素なので u↦N′u mod M′u\mapsto N'u\bmod M' は全添字の置換であり、値が等しい要素も位置ごとに一度ずつ残る。B′B' はクラスごとに作り直す配列で、表記では rr を省略している。

最初に必要なのは Bj mod M′(r)B^{(r)}_{j\bmod M'} である。その位置 sjs_j は N′sj≡j(modM′)N's_j\equiv j\pmod{M'} を満たす。M′>1M'>1 なら、N′d≡1(modM′)N'd\equiv1\pmod{M'} を満たす逆元 d=(N′)−1 mod M′d=(N')^{-1}\bmod M' を使って

sj=jd mod M′s_j=jd\bmod M'

と求める。すると

B(sj+h) mod M′′=B(j+hN′) mod M′(r)B'_{(s_j+h)\bmod M'}=B^{(r)}_{(j+hN')\bmod M'}

であり、A 固定の相手は B′B' 上の開始 sjs_j、長さ cjc_j の連続した円環区間になった。これは整数の割り算 j/N′j/N' ではない。M′=1M'=1 の場合は逆元を使わず、すべて sj=0s_j=0 とする。

実装では逆元を求める代わりに、置換を作るときに逆向きの対応表 pos[N′u mod M′]=u\mathrm{pos}[N'u\bmod M']=u も作れば、sj=pos[j mod M′]s_j=\mathrm{pos}[j\bmod M'] と求められる。この方法なら M′=1M'=1 も同じ処理になる。N′,M′N',M' は全クラスで共通なので、この対応表は一度だけ作ればよい。

巨大な長さは全周回と端数へ分ける

cj=qjM′+ℓjc_j=q_jM'+\ell_j、0≤ℓj<M′0\leq\ell_j<M' と整数の商・余りに分ける。開始位置がどこでも、連続する M′M' 個は全要素を一度ずつ訪れる。従って、x=Aj(r)x=A^{(r)}_j の寄与は

qj∑u=0M′−1min⁡(x,Bu′)+∑h=0ℓj−1min⁡(x,B(sj+h) mod M′′)q_j\sum_{u=0}^{M'-1}\min(x,B'_u) +\sum_{h=0}^{\ell_j-1}\min(x,B'_{(s_j+h)\bmod M'})

となる。全周回を取り除いても開始位置は sjs_j に戻る。端数だけを次の半開区間に分ける。

  • ℓj=0\ell_j=0 なら端数の質問は作らない。
  • sj+ℓj≤M′s_j+\ell_j\leq M' なら [sj,sj+ℓj)[s_j,s_j+\ell_j)。
  • sj+ℓj>M′s_j+\ell_j>M' なら [sj,M′)[s_j,M') と [0,sj+ℓj−M′)[0,s_j+\ell_j-M')。

全周回は区間 [0,M′)[0,M') の質問一つに係数 qjq_j を付け、端数は高々二つの質問にする。各 A 要素から作る質問は合計高々三つで、KK に比例して増えない。

例えば N=4,M=6,K=22N=4,M=6,K=22 なら g=2,N′=2,M′=3g=2,N'=2,M'=3 で、両クラスとも Kr=11K_r=11 である。r=0r=0 では A(0)=(A0,A2)A^{(0)}=(A_0,A_2)、B(0)=(B0,B2,B4)B^{(0)}=(B_0,B_2,B_4) なので B′=(B0,B4,B2)B'=(B_0,B_4,B_2) になる。j=1j=1、つまり A2A_2 を固定すると、d=2,s1=2,c1=5d=2,s_1=2,c_1=5 で次の対応を得る。

局所時刻 tt元の時刻 i=2ti=2t元の B 添字 i mod 6i\bmod6B′B' 上の位置
1222
3600
51041
71422
91800

位置列は 2,0,1,2,02,0,1,2,0 で、一周と端数二つに分かれる。q1=1,ℓ1=2q_1=1,\ell_1=2 より、一周分 [0,3)[0,3) と端数 [2,3),[0,1)[2,3),[0,1) を足せばよい。r=1r=1 でも B′=(B1,B5,B3)B'=(B_1,B_5,B_3) として同じ局所添字を使える。

閾値より小さい値の個数と総和を持つ

残るのは、区間 [L,R)[L,R) と閾値 xx に対する F(L,R,x)=∑u=LR−1min⁡(x,Bu′)F(L,R,x)=\sum_{u=L}^{R-1}\min(x,B'_u) の計算である。Bu′<xB'_u<x ならその値、そうでなければ xx を足すので

F(L,R,x)=S<x(L,R)+x((R−L)−C<x(L,R))F(L,R,x)=S_{<x}(L,R)+x\bigl((R-L)-C_{<x}(L,R)\bigr)

と分けられる。C<xC_{<x} は区間内の xx 未満の要素数、S<xS_{<x} はその値の総和である。求める値そのものを保持しようとせず、閾値で形が切り替わる二種類の寄与を保持する。

各クラス内で質問を xx の昇順、B′B' の位置をその値の昇順に並べる。位置を添字とする二本の Fenwick 木を0で初期化し、質問の直前に未登録の Bu′<xB'_u<x をすべて追加する。一方の木の位置 uu へ1、もう一方へ Bu′B'_u を加える。接頭辞 [0,R)[0,R) と [0,L)[0,L) の差から C<x(L,R),S<x(L,R)C_{<x}(L,R),S_{<x}(L,R) を求め、上式を評価する。全周回の質問は係数を掛け、端数の質問はそのまま、答えを0から加算していく。

値が閾値と等しい位置は、この説明ではまだ木へ追加しない。同じ xx の質問を処理し終えてから、その値の位置を追加してよい。例えば B′=(2,5,2)B'=(2,5,2) の全区間なら、x=2x=2 で C<x=S<x=0C_{<x}=S_{<x}=0 から答えは6、x=3x=3 で C<x=2,S<x=4C_{<x}=2,S_{<x}=4 から答えは7となる。等しい値が複数あっても、位置はまとめずそれぞれ数える。

全クラスの質問を処理した総和を 998244353998244353 で割った余りが答えになる。

典型の発動条件

gcd による周期分解

発動条件: 同じ時刻を二つの周期 i mod N,i mod Mi\bmod N,i\bmod M で参照するとき。

両添字の gcd⁡(N,M)\gcd(N,M) による剰余は一致する。時刻も i=r+gti=r+gt と取り直せば、各クラスは互いに素な周期の問題になる。打ち切り時刻があるときは、元の項数をそのまま使わず各クラスの項数を数え直す。

剰余列の置換

発動条件: 法と互いに素な一定の歩幅で添字を巡回するとき。

訪問順に配列を並べ直すと、算術進行の添字列が円環上の連続区間になる。逆元または逆向きの対応表で開始位置も移す。互いに素でなければ全位置の置換にはならないため、先に gcd ごとのクラスへ分ける。

offline Fenwick sweep

発動条件: 同じ静的配列に対し、区間内の各要素を閾値で切り詰めた値の総和を何度も求めるとき。

閾値順に質問を処理すれば、閾値未満の位置は追加するだけでよい。個数と値の総和を位置ごとに保持し、区間長との差から閾値以上の寄与を復元する。値と質問が同じ閾値に並ぶときは、不等号に合わせて追加と質問の順序を決める。

問題固有の要素

この問題では、全時刻を追う代わりに A の添字を固定すると、B の訪問間隔が一定になる。二周期の組をすべて列挙する必要はなく、各 A 要素につき円環上の開始位置と出現回数だけを残せばよい。

別の問題へ持ち帰る視点は、周期列の値を先にまとめるのでなく、「片方の選択を固定したとき、もう片方をどの順に訪れるか」を調べること。その順序を座標にすれば、疎らな参照を区間質問へ変えられる。

正当性

任意の元の時刻は i=r+gti=r+gt と一意に表せ、0≤i<K0\leq i<K はそのクラスで 0≤t<Kr0\leq t<K_r に対応する。さらに t=j+hN′t=j+hN' と一意に表すと、0≤j<N′0\leq j<N' と 0≤h<cj0\leq h<c_j を得る。従って、クラスと A の局所添字ごとの分割に漏れも重複もない。

M′>1M'>1 では N′sj≡j(modM′)N's_j\equiv j\pmod{M'} より、円環の位置 sj+hs_j+h は元の相手の添字 j+hN′j+hN' に対応する。M′=1M'=1 でも唯一の位置0が対応する。長さ cj=qjM′+ℓjc_j=q_jM'+\ell_j のうち全周回は各位置を qjq_j 回、端数区間は残りの位置を一度ずつ数えるので、元の各項の多重度を保つ。

質問 xx の処理時、二本の Fenwick 木にはちょうど Bu′<xB'_u<x の位置の個数と値が入っている。区間内のそれらは値を、それ以外は xx を寄与するため、S<x+x((R−L)−C<x)S_{<x}+x((R-L)-C_{<x}) は求める区間和に等しい。全周回の係数を掛けてすべての質問を足すと元の和を得る。最後の剰余化は整数の加算・乗算と両立するため、指定された余りを正しく返す。

実装上の注意

  • 負の数の整数除算は言語により床関数と異なる。r≥Kr\geq K なら Kr=0K_r=0、それ以外は 1+(K−1−r)/g1+(K-1-r)/g とし、同様に j≥Krj\geq K_r なら cj=0c_j=0、それ以外は 1+(Kr−1−j)/N′1+(K_r-1-j)/N' と求める。これで K<gK<g や K<NK<N も扱える。
  • M′=1M'=1 では開始0、qj=cj,ℓj=0q_j=c_j,\ell_j=0 で端数はない。円環の折返しを判定するときは sj+ℓj=M′s_j+\ell_j=M' を二区間にせず、半開区間の端として扱う。クラスを移るときは Fenwick 木を0へ戻す。
  • 追加条件を Bu′<xB'_u<x とするなら、等しい値の追加より質問を先に処理する。Bu′≤xB'_u\leq x としても等しい値の寄与は同じだが、その場合は式の個数・総和の定義も「以下」に揃える。
  • Kr,cj,qj,ℓjK_r,c_j,q_j,\ell_j は元の整数から求める。998244353998244353 による剰余を先に取ると、出現回数や周回数が変わる。値のソート・大小比較にも元の Ai,BiA_i,B_i を使う。
  • Fenwick 木の値和は最大 M′×109≤2×1014M'\times10^9\leq2\times10^{14} なので符号付き64 bit整数で保持できる。N′uN'u や jdjd も32 bit整数の積にしない。全周回の寄与をそのまま掛けると総和は最大 102710^{27} になるため、周回数と区間和をそれぞれ 998244353998244353 で割った余りにしてから64 bitで掛ける。各質問の加算でも剰余を取り、巨大な総和を作らない。

復習の核

  • 二周期が重なるときは、共通剰余ごとに時刻も縮約する。配列長だけを割って元の項数を残すと、打ち切り位置を誤る。
  • 等間隔で訪れる添字は、訪問順への並べ替えで連続区間になる。開始位置も同じ写像で移し、N′sj≡j(modM′)N's_j\equiv j\pmod{M'} から復元する。
  • 円環上の巨大な長さは、一周の寄与に商を掛け、余りだけを高々二区間にする。周回数と端数は元の整数から求め、その後の集計で剰余を取る。
  • 最小値の総和では、閾値で寄与が切り替わる点に着目する。小さい値の個数・総和を持てば、大きい側は区間長との差から求められる。

計算量と制約

時間

O((N+M)log⁡(N+M))O((N+M)\log(N+M))。クラスごとの配列長の総和は gN′=N,gM′=MgN'=N,gM'=M で、質問は全体で高々 3N3N 個。逆向きの対応表と配列の構築、質問の生成は O(N+M)O(N+M)、値と質問のソートは合計 O((N+M)log⁡(N+M))O((N+M)\log(N+M))、Fenwick 木への追加と区間集計は合計 O((N+M)log⁡(M′+1))O((N+M)\log(M'+1)) である。gcd の計算もこの上界に収まり、KK に比例する走査は行わない。

空間

O(N+M)O(N+M)。入力配列、並べ替えた配列と位置の対応表、高々 3N3N 個の質問、個数・値和の Fenwick 木を保持する。各クラスの作業領域は使い回せる。

制約との対応

公式制約は 1≤N,M≤2×1051\leq N,M\leq2\times10^5、1≤K≤10181\leq K\leq10^{18}、1≤Ai,Bi≤1091\leq A_i,B_i\leq10^9、時間制限2秒、メモリー制限1024 MiB。処理する位置・質問の個数は N+MN+M に比例し、巨大な KK は64 bit整数の商・余りとしてだけ扱う。縮約後の互いに素という条件が添字置換を保証し、配列長1や出現しない要素も同じ集計へ含められる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: gcd不変量・差分構造

主題
  • gcd不変量・差分構造: gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: gcd不変量・差分構造

    補助タグ: event・値順のオフライン走査 Fenwick Tree・反転数・重み付き接頭辞統計

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

    学習の位置

    体系上の位置: gcd不変量・差分構造

    • gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。

    先に読む単元:

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

    • Bézout係数を求めて一次不定方程式の具体解・一般解を構成する手順は「gcdと整数解の成立条件」で扱う。gcdによる必要条件や剰余類への分解と、解を実際に構成する技能を区別する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題