考察 : グラフへの帰着

各 \(i = 1, \dots, 10^{100}\) に対し、\((i-1) \bmod N\) をそのじゃがいもの「種類」と呼ぶことにします。種類が等しいじゃがいもは重さも等しいです。

高橋くんの作業過程がどのようなものかを (非常に大雑把に) 書くと次のようになります。

最初の箱には種類 \(0, \dots, {a-1}\) のじゃがいもを箱に入れて蓋をする。次の箱には種類 \(a, \dots, b-1\) のじゃがいもを箱に入れて蓋をする。その次の箱には種類 \(b, \dots,c-1\) のじゃがいもを箱に入れて蓋をする。その次の箱には…

流れてくるじゃがいもの重さは周期的なので、箱に入るじゃがいもの個数は最初に入れるじゃがいもの種類によって決まります。そこで、各 \(i = 0, \dots, N-1\) について次の値が求められたとしましょう。

種類 \(i\) のじゃがいもから順番に箱に入れていくとき、何個入れた時点で蓋をされるか？

この値を \(C_i\) とおくと、\(2\) 番目の箱に最初に入れられるじゃがいもの種類は \(C_0 \bmod N\) であり、\(3\) 番目の箱に最初に入れられるじゃがいもの種類は \((C_0 + C_{C_0 \bmod N}) \bmod N\) であり、\(\ldots\) というように決定していくことができます。
このような遷移は、各 \(u \, (0 \leq u \leq N - 1)\) について頂点 \(u\) から頂点 \((u + C_u) \bmod N\) に辺を張った有向グラフ上を移動しているとみなすことができます。

ここまで考察すれば、次の問題とほぼ同じであることに気づくでしょう。

参考 : ABC167-D Teleporter

\(N\) 頂点 \(N\) 辺の有向グラフが与えられる。各頂点 \(u\) に対し、\(u\) を始点とする辺がただ一つ存在し、それは頂点 \(P_u\) に向かって張られている。

頂点 \(1\) からはじめ、現在いる頂点から出ている辺をたどることを \(K\) 回繰り返すと、どの頂点にたどり着くか？

\(i\) 番目のクエリについては、頂点 \(0\) から \(K_i - 1\) 回移動を繰り返してたどり着く頂点を \(u\) としたとき、\(C_u\) が答えとなります。

解法

まず、\(C_i\) を求める方法を説明します。\(S = W_1 + \dots + W_N\) とおいたとき、必ず \(C_i \geq N \times \left\lfloor \frac{X}{S} \right\rfloor\) が成り立ちます。この値をあらかじめ全ての \(C_i\) に加えておくことにすると、残った \(X \bmod S\) の分は \(X \lt S\) の場合に帰着されます。\(X \lt S\) ならば \(C_i \lt N\) であるので、尺取法を用いると \(O(N)\) で全ての \(C_i\) を計算することができます。
簡潔に実装するためのテクニックを紹介します。\(W\) と等しい列を \(2\) 周並べたものを \(W'\) とおき、尺取法を次のように行います。

• \(r := 0, s := 0\) とおく。
• \(l = 0, 1, \dots, N-1\) の順に次を行う。
  • \(r < l\) ならば、 \(r\) を \(l\) で、\(s\) を \(0\) で置き換える。
  • \(s \lt X\) である間、「\(s\) に \(W'_r\) を加え、その後 \(r\) を \(1\) 増やす」ことを繰り返す。
  • \(C_l := r - l\) と定め、\(s\) から \(W'_l\) を引く。

円環上の問題で配列を \(2\) 周分用意しておくと実装が簡潔になる場合があるので、覚えておくと役に立つかもしれません。

次に、前節で構築したようなグラフについて、頂点 \(0\) から \(K\) 回移動を繰り返してたどり着く頂点をクエリあたり \(O(1)\) で求める方法を説明します。頂点 \(0\) から移動を繰り返すと、(鳩の巣原理より) \(N\) 回以内に同じ頂点を \(2\) 度通ります。いずれかの頂点に \(2\) 度目にたどり着く直前まで移動し続けたとき、通った頂点列を \(p_0, \dots, p_{n-1}\) とおくと、以下が成り立ちます。

• \(n \leq N\)
• \(p_0 = 0\)
• \(p_i\) は互いに異なる
• \(p_{n-1}\) から移動した先の頂点は \(p_i\) のいずれかと一致する

\(p_{n-1}\) から移動した先の頂点が \(p_m\) であるとします。このとき、\(p_m, p_{m + 1}, \dots, p_{n-1}\) はサイクルをなします。よって、求めるべき頂点は以下のようになります。

• \(K \lt m\) ならば \(p_{K}\)
• \(K \geq m\) ならば、\(K-m\) を \(n-m\) で割った余りを \(r\) とおいたとき、\(p_{m + r}\)

従って \(p_0, \dots, p_{n-1}\) および \(m\) の値がわかっていればよく、これは \(O(N)\) で前計算しておくことができます。

以上より、この問題を \(O(N + Q)\) で解くことができました。

実装例 (C++)