Observation: boiling down to a graph problem

For \(i = 1, \dots, 10^{100}\), let us call \((i-1) \bmod N\) the “kind” of the potato. Two potatoes with the same kind has the same weight.

Takahashi’s process can be (very roughly) described as follows:

Put potatoes of kinds \(0, \dots, {a-1}\) to the first box and seal it. Put potatoes of kinds \(a, \dots, b-1\) to the next box and seal it. Put potatoes of kinds \(b, \dots,c-1\) to the next box and seal it. Put potatoes …

Since the weights of potatoes are periodical, the number of potatoes in a box is determined by the kind of the first potato to be put. Suppose that we have found the following value:

If we start with putting a potato of kind \(i\), how many potatoes are in the sealed box?

Let \(C_i\) be this value, then the kind of the first potato in the \(2\)-nd box is determined to be \(C_0 \bmod N\), that in the \(3\)-rd box to be \((C_0 + C_{C_0 \bmod N}) \bmod N\), \(\ldots\), \(\ldots\) and so on.
Such process can be regarded as a traversal on a directed graph where there is an edge from Vertex \(u\) to Vertex \((u + C_u) \bmod N\) for each \(u \, (0 \leq u \leq N - 1)\).

Now we can realize that this is almost as same problem as the following:

c.f. ABC167-D Teleporter

You are given a directed graph with \(N\) vertices and \(N\) edges. For each Vertex \(u\), there is a unique edge starting from \(u\), which ends at Vertex \(P_u\).

Starting from Vertex \(1\), repeatedly traverse the edge incident from the current vertex \(K\) times. Which vertex do you end up?

For the \(i\)-th query, the answer is \(C_u\), where Vertex \(u\) is the vertex you end up as a result of traversing an edge \((K_i-1)\) times from Vertex \(0\).

Solution

First, we will explain how to find \(C_i\). Let \(S = W_1 + \dots + W_N\), then it always holds that \(C_i \geq N \times \left\lfloor \frac{X}{S} \right\rfloor\). We can add this value to every \(C_i\) beforehand so that the remaining \(X \bmod S\) part is boiled down to the \(X \lt S\) case. If \(X \lt S\), then \(C_i \lt N\), so with the “sliding window” technique, we can find all \(C_i\) in a total of \(O(N)\) time.
We will introduce a technique for a simple implementation. Let \(W'\) be a concatenation of two copies of \(W\), and do the sliding window trick as follows:

• Let \(r := 0, s := 0\).
• For \(l = 0, 1, \dots, N-1\), do the following:
  • If \(r < l\), then replace \(r\) with \(l\) and \(s\) with \(0\).
  • While \(s \lt X\), repeatedly “add \(W'_r\) to \(s\) and increase \(r\) by one.”
  • Let \(C_l := r - l\), and subtract \(W'_l\) from \(s\).

When it comes to a problem on a cycle, two copies of the array may simplify the implementation, so it is worth learning.

Next, on the graph constructed in the last section, we will introduce how to find the vertex you end up when you traverse an edge \(K\) times starting from Vertex \(0\), in an \(O(1)\) time per query. If you repeatedly traverse an edge from Vertex \(0\), (by the pigeonhole principle) you will always visit a same edge within \(N\) moves. Let \(p_0, \dots, p_{n-1}\) be the vertices you visited before you arrive at the same vertex for the second time, then the following holds:

• \(n \leq N\)
• \(p_0 = 0\)
• \(p_i\) are pairwise distinct
• the edge from \(p_{n-1}\) ends at one of \(p_i\)

Suppose that there is an edge from \(p_{n-1}\) from \(p_m\). Then, \(p_m, p_{m + 1}, \dots, p_{n-1}\) forms a cycle. Therefore, the desired vertex is:

• \(p_K\) if \(K \lt m\)
• \(p_{m + r}\) if \(K \geq m\), where \(r\) is the remainder when \((K-m)\) is divided by \((n-m)\).

Therefore, all we need is the values of \(p_0, \dots, p_{n-1}\) and \(m\), which can be precalculated in a total of \(O(N)\) time.

Therefore, the problem has been solved in a total of \(O(N+Q)\) time.

Sample code (C++)