Regarding the change as paying negative number of coins, the problem statement can be rephrased as follows:

• Print the number of integer sequences \(x_1, x_2, x_3, \dots, x_N\) such that:
  • \(-\frac{A_{i + 1}}{A_i} \lt x_i \lt \frac{A_{i + 1}}{A_i} (1 \le i \lt N)\)
  • \(\sum_{1 \le i \le N} A_ix_i = X\)

If we fix some \(y\), one can uniquely determine the combinations of coins that Lunlun will pay and that clerk returns, thus \(x\) is uniquely determined; conversely, once \(x\) is fixed, \(y\) is also determined, so the paraphrase is valid.

Consider deciding \(x\) one by one in the decreasing order of \(x\). Assume that we have determined \(x_i\). Let \(d = (\sum_{j \ge i} A_jx_j) - X\). (That is, \(d\) is the difference between the balance so far and the target balance \(X\).) Since \(|\sum_{j \lt i} A_jx_j| \lt A_i\), it is necessary that \(|d| \lt A_i\) in order to make \(d = 0\) ultimately. Since \(\sum_{j \ge i} A_jx_j\) is a multiple of \(A_i\), there are at most two integers for \(d\) such that \(|d| \lt A_i\).

With this observation, the following DP is available. dp[\(i\)][\(j\)] : The number of possible combinations of \((x_i, \ldots, x_n)\) such that \(d = j\)

Here, \(j\) can be a large number like \(10^{15}\), but note that for each \(i\) there are at most two \(j\)’s. Therefore, it is good idea to use associated arrays for the second dimension. Transition from dp[\(i\)][\(j\)] depends on the choice of \(x_i\), which is done by considering if it is possible to transition to each of at most two \(j\)’s corresponding to \(i+1\).

Therefore, each transition is done in \(O(1)\) time, and the entire problem can be solved in a total of \(O(N)\) time.