Scofield11's blog

By Scofield11, history, 3 months 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

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Answers to your queries

That's it I guess the things you need to know about this task :)

EDIT: AtCoder people are so generous that they have some prewritten code available on their github. Here and my submission using this code Here
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have seen many codes but I just don't understand them because everyone keeps using some advanced ugly shortcuts.

    I don't understand your solution at all and the link to binomial coefficient doesn't give any implementation that would help me solve this problem.

    I need a code that I can understand

»
3 months 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does this course explain your inverse factorial stuff ?

    • »
      »
      »
      3 months 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.

  • »
    »
    3 months 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...

»
3 months 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.