Counting Dice Rolls — Solution & Editorial

Back to the Problem

A DP over (dice used, running sum) is O(D·T·F); the inclusion–exclusion formula ∑(−1)^jC(D,j)C(T−jF−1, D−1) is O(T/F).

Complexity: O(D·T·F) or O(D)