数列 \(A = (A_1, \ldots, A_N)\) に対して、\(\sum_{i=1}^N x_iA_i\)（ただし \(x_i\in \{0,1\}\)）の形の和を、本解説では \(A\) の部分和ということにします。

---

[1] 石の配置と部分和問題

左から数えて \(1\) 番目と \(2\) 番目の石の間隔が \(a\)、\(2\) 番目と \(3\) 番目の石の間隔が \(b\) であるような状態を \((a, b)\) と表すことにします。以下の解説では \(\gcd(a,b) = 1\) を仮定します。

左右の順番を無視すれば、状態 \((a, b)\) は互除法と同じように変化していきます。この状態に加えて、中央の石の座標がどのように変化するかを図示すると、例えば次の図のようになります。各状態における中央の石の座標の数え上げは、ある数列の部分和の種類数の数え上げに帰着できることがわかります。

状態 \((1,1)\) における数列を \(A\) とします。上の例では、\(A = (7,3,3,1,1)\) です。本問題を解くには、\(A\) の各 prefix についておよび、\(A\) に \(1\) を追加したものについて、部分和の種類数が数えられればよいということになります。

---

[2] 数列 \(A\) の部分和の数え上げ

数列 \(A\) の性質を観察することで、高速に部分和の種類数を計算しましょう。\(A\) の同じ数をまとめて次のように書くことにします。

• \((\underbrace{a_1, \ldots, a_1}_{n_1}, \underbrace{a_2, \ldots, a_2}_{n_2}, \underbrace{a_3, \ldots, a_3}_{n_3}, \ldots, \underbrace{a_{k-1}, \ldots, a_{k-1}}_{n_{k-1}},\underbrace{a_k, \ldots, a_k}_{n_k})\)

この数列は、次の性質を持ちます：

• \(a_1 > a_2 > \cdots > a_k = 1\)
• \(a_i = n_{i+1}a_{i+1} + a_{i+2}\) (\(1\leq i\leq k - 2\))
• \(a_{k-1} = n_ka_k + 1\)

特に \(2\) 番目の性質により、\(n_{i+1}a_{i+1} + a_{i+2}\) を \(a_i\) に取り換える操作を考えることで、部分和を考える部分列を次を満たすものに限定することができます。

• 条件 (\(*\))：\(n_{i+1}\) 個の \(a_{i+1}\) とひとつ以上の \(a_{i+2}\) を使うならば、\(n_i\) 個の \(a_i\) を使う。

さらに、この性質を満たす部分和はすべて相異なることが証明できます（ただし、同じ項が並ぶ部分列は、選ぶ項の位置が違っても同じであると見なします）。

実際より強く、部分列の辞書順と部分和の順序が一致することが、\(k\) に関する帰納法により示せます。\((\underbrace{a_2, \ldots, a_2}_{n_2}, \underbrace{a_3, \ldots, a_3}_{n_3}, \ldots, \underbrace{a_{k-1}, \ldots, a_{k-1}}_{n_{k-1}},\underbrace{a_k, \ldots, a_k}_{n_k})\) の場合の結論を仮定して、\(a_1 = n_2a_2 + a_3 = n_2a_2 + n_4a_4 + a_5 = \cdots\) を用いると、条件 (\(*\)) のもとでは \(a_1\) を使う個数が多い部分列の方が和が大きいと言えるためです。

結局、数列 \(A\) あるいはその prefix に対する部分和の種類数の計算は、条件 (\(*\)) を満たす部分列の数え上げに帰着できることが分かりました。

---

[3] 数列 \(A\) の末尾に \(1\) を加えた場合

次に状態 \((1,0)\) および \((0,1)\) の場合の部分和問題を解きます。つまり、[2] で調べた数列 \(A\) の末尾に \(1\) を追加した数列に関する部分和の種類数の数え上げです。

このとき、数列の項が増えたことによる部分和の種類数の増加は \(1\) （数列全体の和に対応するもののみ）であることが証明できます。

実際まず、\(1\) を使い切らないような部分和は考える必要がありません。\(1\) を使い切って \(a_{k-1}\) を使い切っていないような部分和については、\(1\) を \(a_{k-1}\) に置き換えることができるので、\(a_{k-1}\) も使い切るとしてよいです。あとは条件 (\(*\)) の導出と同じようにして、新しい部分和はすべての項を使い切る場合に限られることが確かめられます。

結局、状態 \((1,0)\), \((0,1)\) に対する部分和の種類数は、状態 \((1,1)\) に対する部分和の種類数に \(1\) を加えたものだと分かりました。

---

[4] まとめ

結局、本問は、数列 \(A\) の各 prefix に対して条件 (\(*\)) を満たす部分列を数えることで解くことができます。これは、現時点で考えている末尾数種類の \(a_i\) について、すべての \(a_i\) を使い切っているかなどを状態とする DP により計算できます。

prefix は \(n_1 + \cdots + n_k\) 個ありますが、同じ \(a_i\) に対応する \(n_i\) 個をまとめて計算するのも容易です。以上をまとめると、\((b-a, c-b)\) に対する互除法のステップ数を \(k\) とするとき、本問題は \(O(k)\) 時間で解けることが分かります。したがって本問題はテストケースごとに \(O(\log(c-a))\) 時間で解くことが出来ます。