wfe2017's blog

By wfe2017, history, 8 years ago, In English

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.net/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?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how about if the number (either the upper or the lower number) could be up to a billion?