お釣りが返ってくることをマイナス枚払ったことと考えると問題文は以下のように言い換えられます。

• 次の条件を満たす整数列 \(x_1, x_2, x_3, \dots, x_N\) の数を出力せよ
  • \(-\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\)

\(y\) が \(1\) つ決まればルンルン君の支払うコインの組み合わせも店員がお釣りを返すコインの組み合わせも一つに定まるため \(x\) も一つに定まり、逆に \(x\) を一つ決めれば \(y\) も定まるのでこの言い換えは正しいです。

\(x\) を添字の大きい順に決め、\(x_i\) まで決めた状況を考えます。
\(d = (\sum_{j \ge i} A_jx_j) - X\) とします。( つまり \(d\) はいままでの収支と目標となる収支 \(X\) との差です )
\(|\sum_{j \lt i} A_jx_j| \lt A_i\) なので最終的に \(d\) を \(0\) にするためには \(|d| \lt A_i\) となっている必要があります。\(\sum_{j \ge i} A_jx_j\) は \(A_i\) の倍数しかとれないので \(|d| \lt A_i\) を満たす \(d\) は高々 \(2\) つです。

これを踏まえると以下のような DP が立ちます。
dp[\(i\)][\(j\)] : \(x_i\) まで決めた状態で \(d = j\) なものの数

ここで \(j\) は \(10^{15}\) などの大きい数になり得るが、 \(i\) が一つ定まるとあり得る \(j\) は高々 \(2\) つなことに注意してください。
よって二次元目は連想配列を使うとよいです。
dp[\(i\)][\(j\)] からの遷移は\(x_i\) を決めることによりますが、\(i + 1\) に対応する高々 \(2\) つの \(j\) についてそれぞれ遷移可能かを考えることで可能です。

よって遷移は \(O(1)\) 、全体で \(O(N)\) で解けます。