Scofield11's blog

ABC 156 — D
By Scofield11, history, 4 years ago, In English

I'm having problems understanding how to solve this problem https://atcoder.jp/contests/abc156/tasks/abc156_d

I've seen a lot of solutions, I've checked almost everything on the internet but nothing helps me because I simply don't understand a single algorithm used in this problem.

I've never used fast exponentiation, extended euclidean algorithm, inverse modulo, lucas theorem or whatever other algorithm I need for this problem before, and I'm having problems understanding what to use, which to use, and how to implement it.

I understand fast exponentiation and I think I can calculate 2^N in this problem, but I don't how to calculate binomial coefficients of N over a and N over b, could anyone help ?

And please understand that I'm really unfamiliar with these kinds of math problems, but I'm starting to learn them, so please make implementation as simple as possible.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I am assuming that you have already figured out that answer will be 2^n — nCa-nCb -1 ; The normal technique of computation of nCr will not work here because n is of the order 10^9 and we cannot compute factorial[n] for such large number (TLE).
we can write nCr= (n*(n-1)*(n-2)*....*(n-r+1))/(1*2*3* ..... r) we can compute the numerator by simple multiplication in this question and for the denominator, we can use the precomputed inv_factorial[r] because r is of the order 10^5; solution to learn these basic concepts that you mentioned follow this

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

    Does this course explain your inverse factorial stuff ?

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

      That is nothing special; that's just part of the modular Arithematic, so Yes, once you know about modular Arithematic and modulo multiplicative inverse you can easily compute (fact[n] mod m),(inv_factorial[n] mod m),(2^n mod m), etc.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We have to choose one or more hence answer will be (2^n)-1-nCa-nCb...

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to ask the same questions too.Because I think this will refers to DFS,but I don't exactly know how to do it.

→ Reply