Linear diophantine equation in non-negative integers
I am not an expert on this at all, but I would like to get a constructive discussion started. Here is an attempt, based on the math.stackexchange.com question Count the number of positive solutions for a linear diophantine equation. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above.

Define $N(a_1, a_2, \ldots, a_n; b)$ to be the number of non-negative solutions of the Diophantine equation
$$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$$
where coefficients $a_i$ are positive and $b$ is non-negative. If I am getting my recursions right, then we have
$$N(a_1; b) = \begin{cases}
1 &amp; \text{if $a_1 \mid b$} \\\\
0 &amp; \text{otherwise}
\end{cases}$$
and
$$N(a_1, \ldots, a_{n+1}; b) = 
\sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)
$$
Now, the sum is a bit long (measured in terms of the length of the input), but we might hope to find a better way of computing it than to actually run through all the $k$'s. We know it's going to be a polynomial in $b$, but I do not see how to compute the polynomial fast enough.