Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.