EXPTREE - Editorial

@bansal1232 No gcd in this case will not at all be 1 (in all cases may be in some) but the thing is you don’t need them to be 1 because
8/2%5=4 and 4/1%5=4.

1 Like

5^-1 gives 400000003, multiply it by 6 and then take mod. You’ll get the desired op.

you can find inverse using fermat’s theorem in logN time.

t test cases. so t*log 10^7 gives time out. O(n) compute (ony one time for n=2 to n=1000),store and then using it is more faster.

It didnt gave TLE to me when i did the same @rj25 . In fact, code passed well within the time limit.

@vijju123 can you give link to your solution ?https://www.codechef.com/viewsolution/14488182 My solution using that approach only gave me 10 points. But @vijju I think my final approach is much faster than O(log n) one.

https://www.codechef.com/viewsolution/14495303

Here @rj25

Your solution is much simpler than mine. I have complicated everything by not taking n%m right from start.

1 Like

I have added an extra small explanation

I have added an extra small explanation

I have added extra explanation, and also a note :slight_smile:

Sure you are right, but in description gcd(P,Q) = 1 so just being precise

Sure you are right, but in problem’s description gcd(P,Q) = 1 so just being precise

1 Like

see this if you did not learn mod inverse

I tried to explain it as much as possible, If you don’t understand at all why are we doing this you should check the link I have added right now (linearity of expectation)

Okay,thanks!

Under the rules of long contests, “it is alright to refer to tutorials, books and other materials, learn a concept and then apply the same to solve a problem during a contest.” Hence it’s fine to do research as long as you do it on your own and you don’t actively discuss with other participants.

1 Like

That’s fair enough. Although in this particular case the paper starts with stating a few results, the formula required to solve the problem among them, and one would be able to use it without going through the rest of the paper to follow the derivation.

http://cs.lmu.edu/~ray/notes/orderedtrees/
This should help.

Thanks mate. Saw this but couldnt understand much. I dont seem to understand the concept behind the word ordering.