Блог пользователя Scofield11

Автор Scofield11, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Does this course explain your inverse factorial stuff ?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.