\(i\) 円硬貨を \(0\) 枚以上 \(A_i\) 枚以下使うことに対応する母関数は

\[ \sum_{j=0}^{A_i} x^{ij} = \frac{1-x^{i(A_i+1)}}{1-x^i} \]

です。これを全ての \(i\) について、総積を取った際の \(x^N\) の係数が答えとなります。整理すると、答えは

\[[x^N] \prod_{i=1}^{N} \frac{1-x^{i(A_i+1)}}{1-x^i} \]

です。ここで explog テクニックというものを使います。上の式を \(\exp(\log(x))\) と合成してみます。

\[ \exp\left(\log\left(\prod_{i=1}^{N} \frac{1-x^{i(A_i+1)}}{1-x^i} \right)\right) = \exp\left( \sum_{i=1}^{N} \left(\log\left(1-x^{i(A_i+1)}\right) - \log\left(1-x^i\right)\right) \right)\]

\(\exp\) の中身を求めることを考えましょう。ここで、\(\log(1-x) = \sum_{i \ge 1} \frac{-x^i}{i}\) であることを利用すると、\(\exp\) 内部の sum は愚直に計算しても調和級数で計算量を \(\mathrm{O}(N \log N)\) に抑えられます。後は \(\exp\) を計算すればよく、これも \(\mathrm{O}(N \log N)\) で行うことが出来ます。