What are some tricks that we can use to find binomials faster? Usually, I just "exploit" some condition, which is like the binomials are not far from each other.
You could see the code here: http://codeforces.com/contest/785/submission/25528358
(This is for round 404, problem D)
What other tricks are there? I saw that other users' code aren't that long, but I don't really understand the codes. Note that for this problem, a naive implementation for the binomial coefficient would fail.
The only trick I know is getting a binomial from a nearby binomial by incrementing/decrementing the numerator and the denominator. Like for example, to transform 69C7 to 75C4, we do 69C7 -> 70C7 -> 71C7 -> ... -> 75C7 -> 75C6 -> 75C5 -> 75C4; it is easy to get the conversion factors from aCb to (a+1)Cb, or (a-1)Cb.
But the problem is that the code here is long. Are there more elegant ways to get binomials faster?
Well, you could do some preprocessing, and calculate the factorials for all numbers from 1 to 200000 (the maximum range for problem D), as well as their modular inverse under 10^9+7, in O(200000). Then you are able to answer any query in O(1). See rajat1603's code for reference.
how about if the number (either the upper or the lower number) could be up to a billion?