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.
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.