Funcia
Lv.3combinatoricsmathmodular-inverse

Binomial Coefficient Queries

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

For each query [n, r] return (nr) mod 1,000,000,007\binom{n}{r} \bmod 1{,}000{,}000{,}007.

Examples

queriesresult
[[5, 2], [10, 0], [10, 10], [6, 3]][10, 1, 1, 20]
[[1000000, 500000]][996692777]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(queries: int[][]) → int[]

Constraints

  • 1≤1 \le queries.length ≤100,000\le 100{,}000, 0≤r≤n≤1060 \le r \le n \le 10^6

Expected complexity

Time
O(MAX_N + Q)
Space
O(MAX_N)

Examples

queriesExpected
[[5,2],[10,0],[10,10],[6,3]][10,1,1,20]
[[1000000,500000]][996692777]

Hint

Hint

Precompute factorials and inverse factorials modulo the prime (one Fermat inverse, then inv_fact[i-1] = inv_fact[i] · i) and answer each query as fact[n] · inv_fact[r] · inv_fact[n-r]. Recomputing each coefficient is O(Q⋅N)O(Q \cdot N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251578 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness405verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.