Count the ways to choose
Counting problems often ask in how many ways items can be chosen out of when the order of the chosen items does not matter. From the five items 1, 2, 3, 4 and 5, for example, there are ten ways to choose two:
The pair is the same choice as , so it appears once. This count is the binomial coefficient , read " choose ", so . Two values hold for every : , since there is one way to choose nothing, and , since there is one way to take everything.
Binomial coefficients grow quickly ( has 30 digits), so judges ask for them modulo a prime:
Answer questions. Each gives integers and ; print modulo .
The first line holds , and each of the next lines holds and .
Constraints
Sample · Input
3 5 3 8 1 9 5
Output
10 8 126
There are two ways to compute them. Pascal's rule computes binomial coefficients with additions only and is enough when is at most a few thousand. The factorial formula, with its divisions done by modular inverses, handles up to a million.
Pascal's rule
Pick one of the items and call it the special one. Every choice of items either contains the special item or does not. If it does, the other chosen items come from the remaining . If it does not, all come from the remaining . No choice is of both kinds, so the two counts add:
In the example, let 5 be the special item. Four of the ten pairs contain it, one for each way to choose its partner from 1, 2, 3 and 4, which is . The other six pairs are the ways to choose two of 1, 2, 3 and 4, which is .
This is Pascal's rule. Written out with one row for each and with counted from 0 along the row, the values form Pascal's triangle. Each entry is the sum of the entry above it and the entry above and to the left, and every row starts and ends with 1:
Pascal's rule needs only additions, so it works under any modulus with no division at all. We fill the table row by row and reduce each sum:
MOD = 10**9 + 7
def pascal(n):
rows = [[1]]
for i in range(1, n + 1):
prev = rows[-1]
row = [1] * (i + 1)
for k in range(1, i):
row[k] = (prev[k - 1] + prev[k]) % MOD
rows.append(row)
return rows
choose = pascal(9)
print(choose[5][2], choose[5][3], choose[8][1], choose[9][5])The program prints 10 10 8 126: the example, then the three sample answers.
The program prints 10 10 8 126: the example, and then the three answers of the sample.
The table for every up to has about entries. That is 12.5 million for . As 64-bit integers they take about 100 MB, which fits in the 512 MB memory limit of CSES. A Python list of lists takes about five times as much, 500 MB for , so in Python a table this large may not fit. For the of Binomial Coefficients it is
too many to compute and far too many to store. For that problem we need a formula that gives one binomial coefficient without the rows above it.
The factorial formula
The product is written and read " factorial". It counts the orders in which items can stand in a line: there are choices for the first place, for the second, and so on. By convention .
Factorials give a second way to count choices. To choose 2 of the 5 items, we can line up all five and take the first two in the line. There are line-ups, but many of them give the same choice. The two chosen items can stand in orders at the front, and the three others in orders behind them, without changing which items were chosen. So each choice is produced by line-ups, and the number of different choices is . The same count for any and gives the formula
Under a prime modulus each division becomes a multiplication by a modular inverse, :
For example, modulo 7, leaves 1, has the inverse 4, and has the inverse 6, so . The exact value, 10, also leaves 3.
The formula has one condition. A multiple of has no inverse, so the factorials we invert must not be multiples of . The formula inverts and , and the tables in the next part compute every inverse from the inverse of , so must be free of the factor as well. A product of whole numbers contains the prime only when one of its factors does, so is free of exactly when . With and up to we are safe. With the tables stop working at , because contains the factor 7 and reduces to 0.
Precompute the factorials and their inverses
Binomial Coefficients asks questions. The card writes the binomial coefficient as , so its is our and its is our , and can be . Multiplying out again for every question could take
Most of that work repeats, since is times 6. We compute every factorial once and keep them in an array fact, where fact[i] is . Each entry is the one before it times , so the whole array costs one multiplication per entry.
Each question then needs the inverses of two factorials. A fast power for each costs about 60 multiplications, which would pass here, but a second table brings a question down to two multiplications. That table, inv_fact, holds the inverse of every factorial and is filled from the largest index down. One fast power gives the inverse of the largest factorial. After that, since , multiplying the inverse of by cancels the last factor and leaves the inverse of :
For and the two arrays hold these values:
The bottom row was filled from the right: inv_fact[5] is the inverse of 1, which is 1, then , then , then , and so on. The answer for is fact[5] * inv_fact[2] * inv_fact[3], which is , as before.
Look up a binomial coefficient in the tables
The widget shows both arrays for modulo 7. Pick to see the three entries that one question multiplies. The second example uses the real modulus . The third takes past the prime 7, where the factorials from on are 0 and the answers come out wrong.
Answer each question with two multiplications
MOD = 10**9 + 7
def factorial_tables(n):
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % MOD
return fact, inv_fact
data = sys.stdin.read().split()
q = int(data[0])
pairs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(q)]
fact, inv_fact = factorial_tables(max(a for a, b in pairs))
for a, b in pairs:
print(fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD)On the sample input the program prints 10, 8 and 126.
The program reads all the questions first and builds the tables up to the largest among them. The answer line reduces after the first multiplication so that no intermediate number grows past about .
Cost of the two methods
- Pascal's triangle up to $N$
time and memory - About additions, which is fine for up to a few thousand.
- Factorial tables up to $N$
time, memory - One multiplication for each entry of each table, and one fast power.
- One binomial coefficient from the tables
- Two multiplications.
For Binomial Coefficients the tables take two million multiplications and one fast power, and the questions take more.
Common mistakes with binomial coefficients
Dividing the remainders with integer division.
- Where it breaks
- Modulo 7, leaves 1 and leaves 5, so dividing the remainders computes
1 // 5, which is 0. But , which leaves 3. - The fix
- Multiply by the inverse factorials:
fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD.
Using the factorial formula when .
- Where it breaks
- Modulo 7, contains the factor 7, so
fact[8]is 0, the fast power forinv_fact[8]returns 0, and every inverse built from it is 0. The formula gives 0 for , which is 8 and leaves 1. - The fix
- Use the formula only with a prime larger than every , as is for . For a small modulus, Pascal's rule still works.
Recall Extend the two tables for $p = 7$ to $n = 6$ and compute $\binom{6}{3}$ modulo 7 from them.
fact[6] is fact[5] times 6, which is . Its inverse is 6, since leaves 1, so inv_fact[6] is 6. Going down from there gives inv_fact[5] as , and the entries below it are the ones we had: inv_fact[3] is 6. The answer is fact[6] * inv_fact[3] * inv_fact[3], which is , so 6. The exact value is , which also leaves 6.