考察
同じ A の要素を使う項だけを集めると、相手の B の添字は一定の歩幅で進む。この「訪れる順」に B を並べ替えれば、巨大な項数を円環の全周回と短い区間に分けられる。まず二つの周期の共通因子を取り除き、一周ですべての位置を訪れる形にする。
求める和は、問題文と同じ0始まりの添字で
である。 は最大 なので、各項の直接走査はできない。組の周期 も最大 に達するため、一周期をそのまま列挙する方針も避けたい。そこで、種類が 個しかない A の添字を固定し、その要素が出る時刻をまとめて扱う。
共通剰余ごとに局所時刻を作る
、、 とおく。時刻を ()と一意に書くと、、 より
となる。つまり、A と B で参照する添字の による剰余は常に同じで、異なる剰余同士の組は現れない。
剰余 の部分列を ()、()とする。このクラスの局所時刻 の個数は、 から
である。よって元の和を、各 についての
に分けられる。 のときは のクラスが空になる。以降は一つの を固定する。縮約後は である。
A を固定した訪問順を円環の連続位置へ移す
を使う局所時刻は と表せる。その出現回数を とすると、 より
で、 が対応する。 の要素は処理しなくてよい。相手の B の添字は と進むので、訪れる順に並べた長さ の配列
を作る。互いに素なので は全添字の置換であり、値が等しい要素も位置ごとに一度ずつ残る。 はクラスごとに作り直す配列で、表記では を省略している。
最初に必要なのは である。その位置 は を満たす。 なら、 を満たす逆元 を使って
と求める。すると
であり、A 固定の相手は 上の開始 、長さ の連続した円環区間になった。これは整数の割り算 ではない。 の場合は逆元を使わず、すべて とする。
実装では逆元を求める代わりに、置換を作るときに逆向きの対応表 も作れば、 と求められる。この方法なら も同じ処理になる。 は全クラスで共通なので、この対応表は一度だけ作ればよい。
巨大な長さは全周回と端数へ分ける
、 と整数の商・余りに分ける。開始位置がどこでも、連続する 個は全要素を一度ずつ訪れる。従って、 の寄与は
となる。全周回を取り除いても開始位置は に戻る。端数だけを次の半開区間に分ける。
- なら端数の質問は作らない。
- なら 。
- なら と 。
全周回は区間 の質問一つに係数 を付け、端数は高々二つの質問にする。各 A 要素から作る質問は合計高々三つで、 に比例して増えない。
例えば なら で、両クラスとも である。 では 、 なので になる。、つまり を固定すると、 で次の対応を得る。
位置列は で、一周と端数二つに分かれる。 より、一周分 と端数 を足せばよい。 でも として同じ局所添字を使える。
閾値より小さい値の個数と総和を持つ
残るのは、区間 と閾値 に対する の計算である。 ならその値、そうでなければ を足すので
と分けられる。 は区間内の 未満の要素数、 はその値の総和である。求める値そのものを保持しようとせず、閾値で形が切り替わる二種類の寄与を保持する。
各クラス内で質問を の昇順、 の位置をその値の昇順に並べる。位置を添字とする二本の Fenwick 木を0で初期化し、質問の直前に未登録の をすべて追加する。一方の木の位置 へ1、もう一方へ を加える。接頭辞 と の差から を求め、上式を評価する。全周回の質問は係数を掛け、端数の質問はそのまま、答えを0から加算していく。
値が閾値と等しい位置は、この説明ではまだ木へ追加しない。同じ の質問を処理し終えてから、その値の位置を追加してよい。例えば の全区間なら、 で から答えは6、 で から答えは7となる。等しい値が複数あっても、位置はまとめずそれぞれ数える。
全クラスの質問を処理した総和を で割った余りが答えになる。
典型の発動条件
gcd による周期分解
発動条件: 同じ時刻を二つの周期 で参照するとき。
両添字の による剰余は一致する。時刻も と取り直せば、各クラスは互いに素な周期の問題になる。打ち切り時刻があるときは、元の項数をそのまま使わず各クラスの項数を数え直す。
剰余列の置換
発動条件: 法と互いに素な一定の歩幅で添字を巡回するとき。
訪問順に配列を並べ直すと、算術進行の添字列が円環上の連続区間になる。逆元または逆向きの対応表で開始位置も移す。互いに素でなければ全位置の置換にはならないため、先に gcd ごとのクラスへ分ける。
offline Fenwick sweep
発動条件: 同じ静的配列に対し、区間内の各要素を閾値で切り詰めた値の総和を何度も求めるとき。
閾値順に質問を処理すれば、閾値未満の位置は追加するだけでよい。個数と値の総和を位置ごとに保持し、区間長との差から閾値以上の寄与を復元する。値と質問が同じ閾値に並ぶときは、不等号に合わせて追加と質問の順序を決める。
問題固有の要素
この問題では、全時刻を追う代わりに A の添字を固定すると、B の訪問間隔が一定になる。二周期の組をすべて列挙する必要はなく、各 A 要素につき円環上の開始位置と出現回数だけを残せばよい。
別の問題へ持ち帰る視点は、周期列の値を先にまとめるのでなく、「片方の選択を固定したとき、もう片方をどの順に訪れるか」を調べること。その順序を座標にすれば、疎らな参照を区間質問へ変えられる。
正当性
任意の元の時刻は と一意に表せ、 はそのクラスで に対応する。さらに と一意に表すと、 と を得る。従って、クラスと A の局所添字ごとの分割に漏れも重複もない。
では より、円環の位置 は元の相手の添字 に対応する。 でも唯一の位置0が対応する。長さ のうち全周回は各位置を 回、端数区間は残りの位置を一度ずつ数えるので、元の各項の多重度を保つ。
質問 の処理時、二本の Fenwick 木にはちょうど の位置の個数と値が入っている。区間内のそれらは値を、それ以外は を寄与するため、 は求める区間和に等しい。全周回の係数を掛けてすべての質問を足すと元の和を得る。最後の剰余化は整数の加算・乗算と両立するため、指定された余りを正しく返す。
実装上の注意
- 負の数の整数除算は言語により床関数と異なる。 なら 、それ以外は とし、同様に なら 、それ以外は と求める。これで や も扱える。
- では開始0、 で端数はない。円環の折返しを判定するときは を二区間にせず、半開区間の端として扱う。クラスを移るときは Fenwick 木を0へ戻す。
- 追加条件を とするなら、等しい値の追加より質問を先に処理する。 としても等しい値の寄与は同じだが、その場合は式の個数・総和の定義も「以下」に揃える。
- は元の整数から求める。 による剰余を先に取ると、出現回数や周回数が変わる。値のソート・大小比較にも元の を使う。
- Fenwick 木の値和は最大 なので符号付き64 bit整数で保持できる。 や も32 bit整数の積にしない。全周回の寄与をそのまま掛けると総和は最大 になるため、周回数と区間和をそれぞれ で割った余りにしてから64 bitで掛ける。各質問の加算でも剰余を取り、巨大な総和を作らない。
復習の核
- 二周期が重なるときは、共通剰余ごとに時刻も縮約する。配列長だけを割って元の項数を残すと、打ち切り位置を誤る。
- 等間隔で訪れる添字は、訪問順への並べ替えで連続区間になる。開始位置も同じ写像で移し、 から復元する。
- 円環上の巨大な長さは、一周の寄与に商を掛け、余りだけを高々二区間にする。周回数と端数は元の整数から求め、その後の集計で剰余を取る。
- 最小値の総和では、閾値で寄与が切り替わる点に着目する。小さい値の個数・総和を持てば、大きい側は区間長との差から求められる。
計算量と制約
時間
。クラスごとの配列長の総和は で、質問は全体で高々 個。逆向きの対応表と配列の構築、質問の生成は 、値と質問のソートは合計 、Fenwick 木への追加と区間集計は合計 である。gcd の計算もこの上界に収まり、 に比例する走査は行わない。
空間
。入力配列、並べ替えた配列と位置の対応表、高々 個の質問、個数・値和の Fenwick 木を保持する。各クラスの作業領域は使い回せる。
制約との対応
公式制約は 、、、時間制限2秒、メモリー制限1024 MiB。処理する位置・質問の個数は に比例し、巨大な は64 bit整数の商・余りとしてだけ扱う。縮約後の互いに素という条件が添字置換を保証し、配列長1や出現しない要素も同じ集計へ含められる。
出典