Binomial coefficient mod p
Compute the binomial coefficient C(n, r) modulo a prime p, where 0 <= r <= n <= 100000 and p is a prime up to 10^9+7. Precompute factorials and inverse factorials so multiple queries would be cheap, but for this signature just return the single value. If r < 0 or r > n, return 0.
Implement
ncr_mod_p(n: int, r: int, p: int) → intExamples
in
[5,2,1000000007]out10What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[5,2,1000000007]10not run yetsample