A non Lucas way of getting AC … Runs in 0.14s and 10.7M … A bit complicated but faster (and the precomputation is the same).
http://www.codechef.com/viewplaintext/6776710
Your solution is O(N). It should get TLE for the last subtask.
Can Anyone help me!!!?
Why is the last subtask wrong?
I only used extended_euclid. Is Lucas’s algorithm different from it?
http://www.codechef.com/viewsolution/6776631
Please tell me my mistake.
You don’t use Lucas’ theorem. O(N) is not optimal
Hi @Adury Surya Kiran/Editors,
I wanna thank you for putting up such a nice Editorial. You have explained everything in detail and I believe it must have taken you a long time to make this editorial. You have turned something complicated and ugly looking into a simple and beautiful solution. 
Thanks again.
Rohit
Hi All,
I am just a newbie here.
I worked on this problem for quite a lot of time. Alas, no result!
Then I observed after the solutions were out, that most of the solvers of this problem had used Lucas theorem.
The theorem I had not heard of, until seeing this editorial and a couple of solutions.
After knowing that this problem needs something that I am missing, the only way I worked was calculating the outputs of some test cases manually and trying to figure some kind of relationship between the inputs and output which came in a form of some series. Though i found a relationship, it was too complex.
Of course, I being a newbie, I could not even think like those experts who solved this.
My question is how can one develop the “instinct” to solve such problems, the “instinct” to apply Lucas Theorem ?
I know its from practice, but unless I know what Lucas theorem is,I cannot imagine how to solve such problem.
And its not the problem with Lucas theorem. Today it was Lucas theorem, tomorrow it maybe another one.
So I am asking about the way how can one approach such problems.
Please can you guide on what all to know before going deeper into competitive programming ,where can I get information on such things(such as approaches/theorems etc) ?
My code TLE C++ on 4.3.2 and AC on C++ 4.9.2. Why is it so?
I am getting a “SIGSEGV” error in the last sub- task. Can anyone please help ?
My solution is :My Solution
I can’t believe I reached the final answer myself!!
But had to take help to calculate choose(n,r) from tester’s solution, for third subtask(Lucas theorem).
If modulus was 10^9+7 instead of 10^6+3 , then what is the method to calculate choose(n,r) where 1<=n,r<=10^9 ?