416. Dice Rolls That Total Exactly
Roll d dice, each with faces numbered 1 to f. Print how many of the
f^d possible outcomes total exactly t, MODULO 1000000007.
Dice are distinguishable, so with two dice 1 then 6 and 6 then 1 are separate
outcomes.
Enumerating outcomes is f^d, which at 30 dice of 30 faces is 30^30, about
2 * 10^44.
The recurrence adds one die at a time:
dp[0][0] = 1
dp[i][s] = sum over face in 1..f of dp[i-1][s - face]
so dp[i][s] counts the ways for the first i dice to total s. The answer is
dp[d][t].
Each layer must be built into a FRESH array read from the previous one. Updating in place lets the same die contribute twice, which counts outcomes that use more dice than exist.
The modulus is not decoration: the true count reaches 10^42 at the stated
bounds, so the answer only exists reduced. Reduce after every addition, and note
that a sum of two values below 10^9 stays inside a 64-bit integer.
Where t is unreachable the answer is 0, which needs no special case: fewer
than d pips or more than d * f simply leaves the entry untouched.
Constraints - `1 ≤ d ≤ 30` - `1 ≤ f ≤ 30` - `1 ≤ t ≤ 1000`
Input
One line containing three integers d, f and t.
Output
Print the number of outcomes totalling exactly t, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.