Coin change problem with specific multiples Background
There are coins with value of 1, 5, 10, 20, 50, 100.
Asking for how many ways are there to make up 10000?

The answer is 174716753951.
As far as I know this is equivalent to finding the 10000th term of the following generating function:
And the formula for general term will be very complicated and can only be solved by recursion.
$$
G(x) = \frac{1}{(1-x) \left(1-x^5\right) \left(1-x^{10}\right) \left(1-x^{20}\right) \left(1-x^{50}\right) \left(1-x^{100}\right)}
$$
But the solution gives a formula, if n is a multiple of 100, then there is:
$$g_{n|100}=\frac{50 n^5}{3}+\frac{475 n^4}{6}+\frac{265 n^3}{2}+\frac{551 n^2}{6}+\frac{137 n}{6}+1$$
The solution does not give more explanation.
Question
I want to know how this polynomial is obtained.
Under what circumstances will I get such a polynomial, I tried $n|50$, and there is no polynomial relationship under 100 degree.
 A: I can give the general strategy, but not the full solution.
In general, if you have a generating function of the form ${P(x)}/{Q(x)}$, where $P(x)$ and $Q(x)$ are polynomials, then you can extract a closed form for the coefficient of $x^n$ by finding the partial fraction decomposition for $P(x)/Q(x)$. If the distinct roots of $Q(x)$ are $r_1,\dots,r_k$, occurring with multiplicities $m_1,\dots,m_k$, then the partial fraction decomposition gives
$$
\frac{P(x)}{Q(x)}=b(x)+\sum_{i=1}^k\sum_{j=1}^{m_i}\frac{a_{i,j}}{(1-x/r_i)^j}\tag1
$$
where $b(x)$ is a polynomial. In the case where $\deg P<\deg Q$, as in your change-making generating function, $b(x)=0$, so I will assume $\deg P<\deg Q$ in the following general discussion.
We can quickly extract the coefficient of $x^n$ using
$$
[x^n]\frac1{(1-x/r)^{j}}=\frac1{r^n}\binom{n+j-1}{j-1}\tag2
$$
Therefore, we can write $[x^n]\frac{P(x)}{Q(x)}$ as a linear combination of powers of roots of $Q(x)$ times certain binomial coefficients. More specifically, $\binom{n+j-1}{j-1}=\frac{1}{j!}(n)(n-1)\cdots(n-j+2)$ is a polynomial in $n$ with degree $j-1$. Therefore, if we combine $(1)$ with $(2)$, and convert all binomial coefficients to polynomials, we get
$$
[x^n]\frac{P(x)}{Q(x)}=\sum_{i=1}^k A_i(n) r_i^{-n},\tag3
$$
where for each $i\in \{1,\dots,k\}$, $A_i(n)$ is a polynomial in $n$ with $\deg A_i=m_i-1$.
Now, consider your problem, where $P(x)=1$ and $$Q(x)=(1-x)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100}).$$
Here, the roots of $Q$ are precisely the $100^\text{th}$ roots of unity. Let $\zeta$ be a primitive $100^\text{th}$ root of unity. Applying $(3)$, we see that
$$
\text{# ways make change for n}=\sum_{i=1}^{100} A_i(n) \zeta^{-in}
$$
This is not quite what you wanted; this is a linear combination of polynomials times exponentials of roots of unity, not just a polynomial. However, in the case were $n$ is a multiple of $100$, all of the $(\zeta)^{-in}$ factors become $1$, so this is just a polynomial, as required.
As you can probably see, all of these steps require a lot of computational effort, so they are best left to a computer algebra system.
