Dice rolls with target sum


Doing this leetcode Fun fact: my first approach to this about a month ago was O(n!)O(n!) with recursion, lets see if I can do better this time.

Let dd be the number of dice rolls, ff be the number of faces and tt be the target sum.

We want to find the coefficient of the xtx^t term in

(i=1fxi)d=xd(i=0f1xi)d=xd(xf1x1)d\left(\sum_{i=1}^f x^i\right)^d = x^d \left(\sum_{i=0}^{f-1} x^i\right)^d = x^d\left(\frac{x^f - 1}{x - 1}\right)^d

Our problem is now reduced to finding the td=:kt-d =: k coefficient in

(xf1x1)d\left(\frac{x^f - 1}{x - 1}\right)^d