Probability and counting DP with modulo in Python

Why this matters

Many questions ask how likely something is. What are the chances that two dice total 7? How many ways can five dice total 20? A probability is a count divided by a total. The total is the number of outcomes that can happen. The count is the number of outcomes that match what you want. When every outcome is equally likely, the probability is a ratio of two counts.

Listing outcomes by hand is slow. Two dice have 36 outcomes, which is easy to list. Twenty dice of 100 faces have 100 to the power of 20 outcomes, which is a 1 followed by 40 zeros. A dynamic programming table counts them without listing them. A dynamic programming table (called a DP table here) is a grid of stored answers, where each answer is built from smaller answers that are already in the grid.

The counts can get very large. Programming contests often ask for the count modulo 1000000007. Modulo means the remainder after division. The remainder of 17 divided by 5 is 2, because 17 is three groups of 5 with 2 left over. In Python the operator is %. If the table takes the remainder after each step, every stored number stays small.

Two more words are used below. Overflow means a number grew bigger than a fixed-size variable can hold, so the stored value wraps around to a wrong number. Python does not have that problem, and Step 3 shows why. The second word is probability. For this lesson it means the count of matching outcomes divided by the count of all outcomes.

The egg drop lesson later in this module also builds a table, but that table counts moves, not outcomes.

Every program in this lesson is a complete Python file that uses only the standard library. Save it as a file, for example main.py, and run it with python3 main.py. The outputs below were produced by Python 3.14.

The idea with one die

A six-sided die shows 1, 2, 3, 4, 5 or 6. Each face is equally likely. There is one way to get a 3, and there are six outcomes in total. So the probability of a 3 is 1 out of 6, written 1/6.

In the code below, faces is the number of faces on each die and dice is the number of dice thrown. One die has faces outcomes. Two dice have faces times faces outcomes, because each face of the first die can appear with each face of the second.

Step 1: Count the totals for two dice

The question is: for each total from 2 to 12, how many outcomes give that total?

Use a table called ways. Let ways[d][t] be the number of ways that d dice add up to the total t. In Python, a list is an ordered container, and the first item has index 0. So ways is a list of counts, and ways[t] is the count for the total t with the dice rolled so far. Two facts start the table.

• With zero dice, the total is 0 and there is exactly one way: throw nothing. So ways[0] is 1.
• With zero dice, no other total is possible. So every other entry is 0.

Now the rule that fills the rest. Look at the last die thrown. It shows some face f from 1 to faces. The other dice must then add up to t - f. So the number of ways is the sum of the old count at t - f, over every face f. If t - f is below 0, that term is skipped, because a total cannot go below 0.

Take the total 7 with two six-sided dice as a worked example. The last die shows a face from 1 to 6. The first die must then show 6, 5, 4, 3, 2 or 1, which is the total 7 minus that face. Each of those six first-die values is reached by exactly one face. So there are 6 ways.

The first die alone gives a count of 1 for each total from 1 to 6, because each face is one way to reach its total. Feed that into the rule and the counts for two dice come out as 1 2 3 4 5 6 5 4 3 2 1 for the totals 2 to 12.

Here is the program. It fills the table one die at a time. Each die needs a new list, so the code creates next_ways and then moves it into ways.

Run it and the output is:

Two six-sided dice, ways to get each total:
  total 2: 1
  total 3: 2
  total 4: 3
  total 5: 4
  total 6: 5
  total 7: 6
  total 8: 5
  total 9: 4
  total 10: 3
  total 11: 2
  total 12: 1
Ways to get 7 out of 36: 6
Probability of 7 as a modular value: 166666668
Check, probability * 36 mod p: 6
pow(36, -1, MOD) gives the same inverse: True
Three six-sided dice, ways to get 10: 27 out of 216
Exact check, three dice total 10: 27
Fifty 20-sided dice match the exact table mod p: True

The table says 6 ways for a total of 7, which matches the hand count. The probability of 7 is 6 out of 36, which reduces to 1/6. The next steps explain the other lines of output.

Notice what count_totals does not do. It never builds a list of the 36 outcomes. It only keeps one list of totals and the list for the previous die.

Step 2: Three dice, a harder example

With three dice, the same rule applies one level deeper. Take the total 10 with three six-sided dice. Look at the first die and its face f. The other two dice must then total 10 - f.

• Face 1: the other two dice total 9. The two-dice counts give 4 ways.
• Face 2: the other two dice total 8. That is 5 ways.
• Face 3: total 7, which is 6 ways.
• Face 4: total 6, which is 5 ways.
• Face 5: total 5, which is 4 ways.
• Face 6: total 4, which is 3 ways.

Add the six numbers: 4 + 5 + 6 + 5 + 4 + 3 = 27. Three dice have 6 * 6 * 6 = 216 outcomes. So the probability of a total of 10 is 27/216. That reduces to 1/8, which is 0.125 as a decimal.

The program prints 27 and 216, which agrees with this hand count. The table does the same sum for every total at once, so it does not need the six separate lookups written out.

Step 3: Why the numbers get too big

Counts grow quickly when the dice are many. Look at 20 dice with 100 faces each. The number of outcomes is 100 to the power of 20, which is a 1 followed by 40 zeros. The count for one total in the middle of that range has 38 digits.

Many languages store whole numbers in a fixed number of bits. A bit is a single binary digit, 0 or 1. A 32-bit integer can hold values up to 2147483647. A 64-bit integer can hold values up to 9223372036854775807. If a sum goes past the top of its range, the stored value wraps around to a wrong number, and the program usually reports no error.

Python does not work that way. An int grows to whatever size its value needs, so the exact count is stored with no modulo. The program below computes the exact table for 20 dice of 100 faces. It then shows what a 32-bit and a 64-bit integer would keep from the same value. The ctypes module in the standard library converts a number to a fixed size the way a C program would, keeping only the low bits.

The output is:

Twenty 100-sided dice, total 1000
  digits in the exact count:   38
  exact value:                 30581640041478060584919034803574871103
  exact value mod p:           64135339
  kept by a 32-bit integer:    -1427303361
  kept by a 64-bit integer:    -3805315028246260673
  2000000000 + 2000000000 in 32 bits: -294967296
  2000000000 + 2000000000 in Python:  4000000000
  -7 % 3 = 2

The 32-bit and 64-bit values are wrong counts. The true count has 38 digits, and the fixed-size types keep only the low bits of it. The 32-bit value is negative, which a count can never be. Python prints the exact count.

The last line shows that % in Python gives 2 for -7 % 3. Python's % takes the sign of the divisor, so for a positive divisor the result is always from 0 up to the divisor minus 1. Many other languages return -1 here. This is why the modular steps in this lesson work in Python without a helper function.

The exact value mod p is 64135339. The modular table in Step 4 gives the same number without ever holding the 38-digit value.

Step 4: Keep every table entry under the modulus

The remainder of a sum equals the remainder of the sum of remainders. In symbols, (a + b) mod p equals ((a mod p) + (b mod p)) mod p. The same is true for products. So the table can take the remainder at every step and still get the right final remainder. That is what count_totals does in its inner loop:

total_ways = (total_ways + ways[total - face]) % MOD

Every value stored in ways is below MOD, which is about one billion. So total_ways + ways[total - face] is below 2 times MOD, which is about 2 billion. Python has no fixed size to run out of, so the sum is safe either way. The % after each addition keeps total_ways below MOD at all times, so the table never holds a big number. That keeps the work fast and the memory small.

The program checks the modular table against the exact table for 50 dice with 20 faces. It prints True, so every one of the 1001 entries matches after the remainder is taken. The same check gave 64135339 for 20 dice of 100 faces, as shown in Step 3.

Cost: the loops visit at most dice times dice * faces totals, and each total adds up to faces values. For 50 dice of 20 faces that is at most 50 * 1000 * 20, which is 1,000,000 additions. That is fast. The cost grows with the square of the number of dice, so the same method becomes slow for much larger inputs.

Step 5: Turning a count into a probability

After the modulo, the table holds a remainder, not a real count. A remainder cannot be divided the usual way. Probability is a division, so we need another tool.

That tool is the modular inverse. The inverse of a number x modulo p is a number y such that x * y leaves remainder 1 when divided by p. Dividing by x then means multiplying by y. When p is a prime number, Fermat's little theorem gives a direct way to find the inverse: compute x to the power p - 2, taking the remainder at each multiplication.

Python has this built in. The three-argument form of pow takes a base, a power and a modulus, and it does the repeated squaring (multiplying a number by itself in doubling steps) for you. The lesson uses it like this:

total_outcomes = 36
inverse = pow(total_outcomes, MOD - 2, MOD)
probability7 = two[7] * inverse % MOD

The result is 166666668. Check it by multiplying back: 166666668 times 36, taken mod p, gives 6. That is the count we started with. Also, 6 times 166666668 is 1000000008, which is 1 more than p. So 166666668 acts as 1/6 in this modulus.

Python 3.8 and later also accept pow(36, -1, MOD), which asks for the inverse directly. That form raises an error when the two numbers share a factor, for example pow(2, -1, 4) gives ValueError: base is not invertible for the given modulus. The MOD - 2 form works whenever MOD is prime, which is the case here.

Do not try to print the modular result as a decimal probability. The number 166666668 is not 0.1666... It is a code for the fraction 1/6 that only makes sense under the modulus. If the question asks for a real probability, use the exact count and divide it by the total, which Python does with /. If it asks for a modular answer, use the inverse.

Worked example: a total that needs a longer chain

Suppose the question asks for the modular probability of a total of 10 with three six-sided dice. The count from Step 2 is 27 and the total is 216. The modular probability is 27 times the inverse of 216, taken mod p. The program does not print this value, but the steps are the same as in the two-dice case, with pow(216, MOD - 2, MOD) in place of the inverse of 36.

The key point is the order of the work. First build the count table with remainders. Then pick out the entry you need. Then multiply by one inverse at the end. Do not take an inverse for each step of the table. The table only adds and multiplies counts, and the division happens once at the end.

Common mistakes

In Python, / always gives a float, and // drops the fraction. Mixing them up gives a wrong answer without an error:

count = 6
total = 36
print("Floor division 6 // 36 gives", count // total)
print("True division 6 / 36 gives", count / total)

The output is:

Floor division 6 // 36 gives 0
True division 6 / 36 gives 0.16666666666666666

Use / when you want the probability as a decimal, and // only when you want a whole-number quotient.

Python lists accept negative index numbers, and a negative index counts from the end of the list. So ways[-1] reads the last item and raises no error. In the table, total - face goes below 0 when the loop tries a face larger than the total. The program then reads the wrong entry, and the result is wrong without a message:

ways = [1, 2, 3]
total = 1
face = 2
print("ways[total - face] with total 1 and face 2 gives", ways[total - face])
 
try:
    print(ways[-10])
except IndexError as e:
    print("IndexError:", e)

The output is:

ways[total - face] with total 1 and face 2 gives 3
IndexError: list index out of range

The first line reads ways[-1], the last item, and gives 3 with no error. The second line uses an index too far below zero for the list, which raises IndexError: list index out of range. The fix is the loop bound min(faces, total) in count_totals, which stops face from going above total.

Python integers do not overflow, so the silent wrap-around from Step 3 does not happen. The cost is different. A count can grow to hundreds of digits, which makes the arithmetic slower and uses more memory. Take the remainder whenever the question asks for a modular answer, and the numbers stay small.

Forgetting the inverse is the last common mistake. A modular table gives a remainder, and the remainder of a count is not a probability. Multiply by the inverse of the total, and check the answer by multiplying back. For the two-dice case, probability7 * 36 % MOD must give 6.

Practice

Exercise 1. Four dice have four faces each, numbered 1 to 4. How many ways can the four dice total 8?

Show the answer

31. One way to see it: the total of 8 is the sum over the face of the first die, using the three-dice counts for totals 7, 6, 5 and 4. Those counts are 12, 10, 6 and 3. The sum is 12 + 10 + 6 + 3 = 31. Call count_totals(4, 4)[8] in a copy of the program to check it.

Exercise 2. Two dice have three faces each, numbered 1 to 3. How many ways can they total 4?

Show the answer

3 ways: 1 and 3, 2 and 2, and 3 and 1. The table rule gives the same value. Each first-die face from 1 to 3 leaves a total of 4 minus that face for the second die, and each of those totals (3, 2 and 1) is reachable in one way.

Exercise 3. With two six-sided dice, the total 2 happens in exactly one of 36 outcomes. Give the modular probability of a total of 2, using the modulus 1000000007.

Show the answer

27777778. This is the inverse of 36 modulo 1000000007, found with pow(36, MOD - 2, MOD). Check it: 36 times 27777778, taken mod the modulus, gives 1.

Exercise 4. In Python, what does -7 % 3 print? Explain the result in one sentence.

Show the answer

2. Python's % takes the sign of the divisor, so for a positive divisor the result is never negative. That is what a modular answer needs.

Exercise 5. Write a function that returns the probability of a total as a float for two dice with faces faces each. Test it with 6 faces and the total 7.

Show the answer

0.16666666666666666. A correct function divides the count by faces * faces with /, for example ways / (faces * faces). Using // would give 0 instead.

Summary

• A probability is a count of matching outcomes divided by the count of all outcomes.
• A table row for d dice is built from the row for d - 1 dice by adding up to faces shifted values.
• Python integers grow to any size, so the exact count is always stored, but large counts make the arithmetic slow.
• Take the remainder after each addition, so every stored value stays below the modulus.
• A modular probability needs the modular inverse of the total, which pow(x, MOD - 2, MOD) gives when MOD is prime.
• Use / for a decimal probability and // only for a whole-number quotient.