Below, for a sequence \(A = (A_1, \ldots, A_N)\), we call a sum of the form \(\sum_{i=1}^N x_iA_i\) (where \(x_i\in \{0,1\}\)) a partial sum of \(A\).

---

[1] Arrangements of the stones and the partial sum problem

Let \((a, b)\) represent the state where the distances between the first and second stones and between the second and third are \(a\) and \(b\), respectively. We assume \(\gcd(a,b) = 1\) below.

If we see the pair as unordered, the state \((a, b)\) changes in a way resembling Euclidean division. In addition to this state, the figure below shows the possible changes in the coordinate of the middle stone. We see that counting the possible coordinates of the middle stone in each state can be reduced to counting different partial sums of a certain sequence.

Let \(A\) be the sequence for the state \((1,1)\). In the example above, \(A = (7,3,3,1,1)\). Our objective is now to count different partial sums of each prefix of \(A\) and \(A\) with \(1\) appended to the end.

---

[2] Counting partial sums of the sequence \(A\)

Let us observe the properties of \(A\) to efficiently compute the number of different partial sums of \(A\). We will put together the same numbers in \(A\) as follows:

• \((\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})\).

This sequence has the following properties:

• \(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\).

Remarkably, the second property enables us to exchange \(n_{i+1}a_{i+1} + a_{i+2}\) for \(a_i\), which allows us to only consider partial sums corresponding to subsequences that satisfy the following.

• Condition (\(*\)): If \(n_{i+1}\) copies of \(a_{i+1}\) and one or more copies of \(a_{i+2}\) are used, \(n_i\) copies of \(a_i\) are used.

Additionally, we can prove that all subsequences with this property have distinct sums (two subsequences are considered the same if their contents are the same, even if they originate from different positions).

Actually, we can even show that the sums are in the lexicographical order of the subsequences by induction on \(k\). If we assume the conclusion for \((\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})\) and use \(a_1 = n_2a_2 + a_3 = n_2a_2 + n_4a_4 + a_5 = \cdots\), we can state under Condition (\(*\)) that the more copies of \(a_i\) a subsequence has, the greater the sum is, completing the proof.

We have now seen that counting different partial sums of the sequence \(A\) or its prefix can be reduced to counting subsequences that satisfy Condition (\(*\)).

---

[3] The sequence \(A\) with \(1\) appended to the end

Next, we will solve the partial sum problem for the states \((1,0)\) and \((0,1)\). That is, we will count different partial sums of the sequence \(A\) with \(1\) appended to the end, which we saw in [2].

Here, we can prove that the addition of a term to the sequence increases the number of different partial sums by \(1\) (nothing other than what corresponds to the sum of the whole sequence).

We begin by noticing that we do not have to consider partial sums that do not use up all \(1\)’s. For partial sums that use up all \(1\)’s but not all \(a_{k-1}\)’s, we can replace \(1\)’s with \(a_{k-1}\)’s, so we can assume that \(a_{k-1}\)’s are also used up. Then, similarly to when we derive Condition (\(*\)), it can be verified that a new partial sum only arises when all terms are used up.

We have now seen that the number of different partial sums for the states \((1,0)\) and \((0,1)\) is equal to that for the state \((1,1)\) plus \(1\).

---

[4] Summary

Eventually, we can solve the problem by counting subsequences satisfying Condition (\(*\)) of each prefix of \(A\). For this, we can use DP with states such as whether all copies are used up for the last few \(a_i\)’s we are considering.

There are \(n_1 + \cdots + n_k\) prefixes, but we can easily process together \(n_i\) of them corresponding to the same \(a_i\). By summarizing the above, the problem can be solved in \(O(k)\) time, where \(k\) is the number of steps in the Euclidean division for \((b-a, c-b)\), that is, \(O(\log(c-a))\) time per test case.