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.

Answers to your queries

Binary exponentiationhttps://cp-algorithms.com/algebra/binary-exp.html

Modulo inversehttps://cp-algorithms.com/algebra/module-inverse.html

Finding Binomial coefficientshttps://cp-algorithms.com/combinatorics/binomial-coefficients.html

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

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

It would be better to be a bit more specific or else how would one know what part you do not understand.

https://pastebin.com/tvcFyYjC

I don't understand how to implement a solution in this code.

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

Does this course explain your inverse factorial stuff ?

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.

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

Yes you are right. I've corrected 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.