What is the time complexity of determining coefficients of generating functions? My question is inspired by the following problem:
Given $k$ coins with denominations $\{c_1, ..., c_k\}$, how many ways are there to generate $n$ cents?
This can be solved in $\Theta(nk)$ time using dynamic programming.  But can also be solved by finding the coefficient of $x^n$ in the generating function $\prod_{i \leq k}  \frac{1}{1-x^{c_i}}$ 
What is the time complexity of such an approach?
How is the time complexity related to which generating function is solved for?
 A: If you're willing to make the complexity worse in $k$ you can make it substantially better in $n$. Suppose we want to extract the coefficient $a_n$ of $x^n$ in the generating function $\frac{P(x)}{Q(x)}$ where $Q$ is a polynomial of degree $d$ with nonzero constant term and $\deg P < \deg Q$. Then, as it turns out, we can write down a $d \times d$ matrix $M$ (the companion matrix of the polynomial whose coefficients are the reverse of $Q$'s) and vectors $v, w$ such that 
$$a_n = v^T M^n w.$$
So the problem reduces to the efficient computation of powers of a matrix, and this can be done efficiently by binary exponentiation. This uses $O(\log n)$ matrix multiplications, but unfortunately the sizes of the entries in general grow exponentially in $n$. 
However, in this case the sizes of the entries grow polynomially in $n$, so the final time complexity is polynomial in both $d$ and $\log n$. 
Example. Let $\frac{P(x)}{Q(x)} = \frac{x}{1 - x - x^2}$ be the generating function for the Fibonacci numbers $F_n$. Then, as it turns out, the matrix we want is $M = \left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$, and it satisfies
$$M^n = \left[ \begin{array}{cc} F_{n+2} & F_{n+1} \\\ F_{n+1} & F_n \end{array} \right].$$
The binary exponentiation strategy above corresponds to repeated use of the duplication formulas
$$F_{2n} = F_{n+1}^2 + F_n^2$$
$$F_{2n+1} = F_{n+2} F_{n+1} + F_{n+1} F_n$$
both of which follow directly from the identity $M^{2n} = (M^n)^2$. 

I should also mention that for fixed $k$ you can in fact write down an explicit quasi-polynomial closed form for the answer, so you just need an efficient algorithm for integer multiplication. 
