dice-combinations

Dice Combinations

CSES easy

You are given an integer \(n\). You repeatedly throw a fair 6-sided die (values \(1..6\)) and sum up the results.

Your task is to count the number of ways to obtain total sum exactly \(n\) by throwing the die one or more times.

Order matters: For example, for \(n = 3\), the valid sequences are:

\(1 + 1 + 1\)
\(1 + 2\)
\(2 + 1\)
\(3\)

So the answer is \(4\).

Input:

A single integer \(n\).

Output:

Print the number of ways (modulo \(10^9 + 7\)).

Constraints:

\(1 \le n \le 10^6\)

Example:

Input:

Output:

Solution

This is a classic 1D dynamic programming problem.

Let’s use the SRTBOT framework to design the DP.

S – State

Define:

\(dp[x] = \text{number of ways to obtain sum } x \text{ using dice throws}.\)

We want to compute dp[n].

R – Recurrence (Relation)

To get sum \(x\), the last die roll could be:

1 → previous sum = \(x-1\)
2 → previous sum = \(x-2\)
…
6 → previous sum = \(x-6\)

So every way to make \(x\) is formed by:

a way to make \((x-k)\) and then rolling a \(k\), for some \(k \in {1,2,3,4,5,6}\).

Therefore:

\(dp[x] = dp[x-1] + dp[x-2] + dp[x-3] + dp[x-4] + dp[x-5] + dp[x-6],\)

where we only include terms with \((x-k) \ge 0\). All operations are done modulo \(10^9+7\).

T – Transitions

From smaller sums to bigger sums:

For each \(x\), we look back at up to 6 previous states:
- \(x \leftarrow x-1, x-2, \dots, x-6\).

These are the edges in our DP graph.

B – Base cases

What about \(dp[0]\)?

There is exactly one way to make sum 0: do nothing (empty sequence).

So:

dp[0] = 1
For \(x < 0\), we treat dp[x] = 0 (no ways to get a negative sum).

All other dp[x] will be computed from the recurrence.

O – Order of computation

We must compute dp[x] in increasing order of x, because dp[x] depends only on smaller sums:

Start from dp[0].
Then compute dp[1], dp[2], ..., dp[n] in order.

dp[0] = 1;
for x in 1..n:
    dp[x] = sum of dp[x-k] for k in 1..6, x-k >= 0

T – Time and Space Complexity

For each x from 1 to n, we consider up to 6 transitions:

Time: \(O(6n) = O(n)\)
Space: \(O(n)\) for the dp array of size n+1.

This is fine for \(n \le 10^6\).

Note

Intuition recap

Break the problem at the last die roll.
State = “number of ways to get a certain sum”.
Each state depends on up to 6 previous sums.
We build answers from 0 up to n.

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1'000'000'007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;  // one way to make sum 0: empty sequence

    for (int x = 1; x <= n; x++) {
        long long ways = 0;
        for (int k = 1; k <= 6; k++) {
            if (x - k >= 0) {
                ways += dp[x - k];
                if (ways >= MOD) ways -= MOD; // avoid overflow
            }
        }
        dp[x] = (int)ways;
    }

    cout << dp[n] << '\n';
    return 0;
}

Caution

Modulo and types

Always take results mod \(10^9+7\).
Use long long while summing (to avoid overflow), then cast back to int.
The DP array can be vector<int> since we always store values < MOD.