考察
指数を時刻順に追うと、大きな歩幅のため剰余が頻繁に折り返すことがある。そこで、少し離れた時刻をたどることで値の変化が小さくなる組を探す。その時刻差ごとに列を分ければ、折返しの少ない等差数列にまとめられる。各列では冪の和が等比数列の和になるため、全項を生成せずに計算できる。
求める和は である。 は最大 なので、各時刻の指数を一つずつ計算する方法では間に合わない。まず周期を取り除き、その後に残った指数をまとめる方法を考える。
gcd縮約で底と周期をそろえる
とし、 と書く。元の指数は必ず と同じ余りを持ち、次のように表せる。
よって、底を 、外に掛ける因子を とすれば、答えは になる。指数の法は 、答えの法は引き続き である。
なら縮約後の指数はすべて0なので、答えは 。これで も扱える。以下は とする。このとき なので、連続する 時刻の剰余は を一度ずつ取る。
と分けると、各完全周回の後は同じ剰余から再開するため、
となる。例えば では 。元の指数は であり、 に対応する和は である。完全周回の個数を元の で割って求めたり、底を元の のままにしたりしない。
以下は端数 項の処理を考える。 なら端数和は0であり、分割自体が不要である。
小さい時刻差から小さい値の変化を作る
と置く。まず、時刻順の列を折返しで切るだけでも等差数列にはなる。しかし歩幅が のままでは、本数が に達する。 が大きいと、ほとんど圧縮できない。
折返しを減らすには、進める歩幅を小さくしたい。隣の時刻にこだわらず、短い区間内で値が近い二点を探す。 とする。 なら各項を直接加算してよい。以下は とする。
最初の 個の組 を値順に並べ、その値を とする。 かつ より、値はすべて異なる。通常の隣接差は 個あり、総和は 。したがって、その最小値 には
が成り立つ。 点から通常の隣接差を取る場合、上界を とはできない。例えば の値は で、最小差3は より大きい。個別公式解説にもこの定数境界があるため、ここでは上の隣接差の総和による論証で補正している。
最小差を与える二点を、今度は時刻順に と並べ、 とする。値順と時刻順は一致するとは限らないので、 となる符号 も保存する。すると
となる。これが、短い時刻差 ごとに進むと、値は小さな歩幅 または で動くという意味である。
時刻を分け、折返し直前までを一度に取る
時刻を ごとに分ける。余り の列は
の 項を持つ。先頭の値は で、値の列は になる。すべての時刻は余りと列内の位置を一意に持つので、この分け方には漏れも重複もない。
例えば では 。最初の値は時刻順に 、値順に という「値・時刻」の組になる。最小差は1で、対応する時刻を と並べ直すと値は と減る。従って である。
各列を一項ずつ進める必要はない。現在値を 、残りの項数を とすると、次の折返しの直前までに取れる項数 は整数除算で求まる。
増加方向では 、減少方向では を満たす最大の項数である。上の の列では、最初は なので 、すなわち を取る。次は となり、残りの を取る。
この 項の和を加算したら、残りを とする。まだ残るなら へ進め、同じ処理を繰り返す。ここで負の剰余も に正規化する。
分割後の本数も確認する。長さ の列が円周上で進む距離は であり、折返し回数は高々 。出発位置によっては最初の一回がすぐ起こるので、この定数1を落としてはならない。初期の 本も合わせた全体の本数は
最後は 、、 を使った。短い区間から対を探す負担と、折返しを処理する負担が、この の選び方で釣り合う。
負方向も、小さい指数からの等比数列として足す
折返しを含まない一片は である。 のまま底を とすると、 の逆元が存在しない場合に困る。しかし和では項の順を変えてよいので、減少列だけ逆順に読む。
小さい方の指数を (増加方向)、(減少方向)とすれば、どちらの寄与も
である。例えば の寄与は 。負の指数も逆元も不要になる。
冪と和を組にして、除算せずに二分累乗する
比を とし、 と置く。 とする。等比数列の公式で を割る方法は、 が合成数だと使えるとは限らない。例えば では に逆元がない。 の場合も同じ実装で処理したい。
長さ の区間を で表す。長さ と の区間をつなぐと、後半の和には を掛けるので、
となる。空区間は 、長さ1は 。長さ1の組を二分累乗すれば、長さ の組を 時間で求められる。例えば は 、 は である。反復で実装すれば補助領域も定数で済む。
これで完全周回分は 、各片の寄与は として求まる。 は全片で共通なので一度だけ計算し、端数和をすべて足した後、完全周回分との和に を掛ければ答えになる。 の場合は分割を省き、端数の各 を通常の二分累乗で足す。
典型の発動条件
Sqrt Heuristic for Floor Sums
線形剰余列で、元の歩幅による折返しが多すぎるときに候補となる。短い区間内の近接二点を値順に探し、時刻差で部分列に分ける。通常の隣接差から得る境界は であり、初期列も含めた本数 を評価して使う。
除算を使わない等比数列和
法が素数とは限らない、または比が1にもなるときは、冪と和を一組にして結合する。後半の和を前半の冪だけずらす操作は加算・乗算だけで閉じるため、逆元の有無によらず二分累乗できる。
問題固有の要素
今回、和の項は指数だけで決まり、時刻順を変えても答えが変わらない。この性質があるから、時刻差で列を分け、さらに減少列を逆順にしてもよい。順序に依存する集計へ転用する場合は、この並べ替えが許されるかを先に確認する。
正当性
gcd縮約の恒等式は元の各項を に一致させる。互いに素な係数では周期内の剰余が全種類を一度ずつ取るため、完全周回を幾何和へ置き換えられる。端数の各時刻は と列内の位置で一意に表され、 より各列は符号付き歩幅 で進む。整数除算で求めた項数は折返しを含まない最大の区間を切り出し、その直後から再開するので、全時刻を一度ずつ覆う。減少列の逆順化は和を保ち、冪と和の結合則は各片の幾何和を除算せず正しく計算する。従って、完全周回と全片の寄与を足して を掛けると元の和を得る。
実装上の注意
- は先に処理する。 なら端数和は0、 なら直接加算とし、 点の選択は の場合だけ行う。
- 値と元の時刻を組で保存する。値順の差 は正だが、時刻順の変化の符号 は別に必要である。
- 区間長は「最後の添字」より1大きい。負方向では としてから非負指数の累乗を使う。
- は と互いに素とは限らず、縮約後の が0になることもある。二分累乗の初期値は常に1とし、指数0の項を保つ。
- 、法 の下での積、完全周回数との積は32 bitに収まらない。制約内では符号付き64 bit整数を使える。JavaScriptの
number では整数精度が足りないため bigint などを使う。負数の % は言語によって負になるので正規化する。
復習の核
- 剰余を時刻順に追って折返しが多いなら、短い区間内で値が近い二点を探し、その時刻差で進んでみる。
- 点が 個なら、通常の隣接差は 個。平方根本数の評価にも、最初からある 本と出発位置の影響を含める。
- 和の順序を変えられるなら、負方向の等差指数列は逆順に読む。逆元を導入する前に、非負指数だけで表せないかを考える。
- 等比数列和で割り算ができないときは、区間の「冪と和」を一緒に結合する。
計算量と制約
時間
縮約後の法を として、1ケースあたり 。全体では を上界とする。
最初の 点の生成・ソートは 。片は 本で、各片の開始指数の累乗と幾何和はそれぞれ 。直接加算する場合も高々 項で同じ上界になる。gcd縮約と の計算に 、完全周回の幾何和に を要する。周回数 は和に掛けるだけなので、 の因子は付かない。
空間
。最初の 個の値と時刻を保存し、各片は列挙した順に集計する。二分累乗は反復で行う。
制約との対応
、、、。 なので であり、指数を最大 項生成する代わりに平方根本数の片を扱う。 の素数性や の可逆性は仮定しない。
出典