Number of Dice Rolls with Target Sum
easyDynamic Programming II+10 XPTime limit 2s
You roll n dice; each die has faces 1 … f. In how many ways can the faces add up to exactly t? The dice are different (die 1, die 2, …), so 1 + 2 and 2 + 1 are different ways. Print the count modulo 1 000 000 007.
Input: one line n f t.
Output: the number of ways modulo 10⁹ + 7.
Constraints: 1 ≤ n ≤ 100, 1 ≤ f ≤ 100, 1 ≤ t ≤ 10⁴.
Think about it: ways[d][s] = ways for the first d dice to sum to s = ways[d−1][s−1] + … + ways[d−1][s−f]. That's O(n · t · f) — fine here — and a prefix sum over the previous row brings it down to O(n · t).
Sample input 1
2 6 7
Sample output 1
6
Sample input 2
1 6 3
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).