The problem
For each pair (n, k) in queries, work out C(n, k), the number of ways to choose k items from n, modulo the prime p. Return the answers as a list, in the same order. C(n, k) is 0 when k is bigger than n.
comb_mod([(5, 2), (6, 3), (4, 0)], 1_000_000_007)
# [10, 20, 1]
comb_mod([(3, 5)], 1_000_000_007) # [0]
math.comb, math.factorial and math.perm are switched off. pow is allowed.
Limits
- Up to 100,000 queries, with 0 ≤ k and n up to 1,000,000.
pis a prime bigger than every n. - Working out each answer from scratch is too slow for 100,000 queries. The big tests have 6 seconds each.
Builds on MATH-6 Combinations and Pascal’s triangle.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
10 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | More than n | Not run | |
| 3 | Nothing from nothing | Not run | |
| 4 | Row 10 | Not run | |
| 5 | A big count | Not run | |
| 6 | Another prime | Not run | |
| 7 | A small prime | Not run | |
| 8 | No queries | Not run | |
| 9 | 100,000 queries | Not run | |
| 10 | The middle of row 10⁶ | Not run |