Another way to derive \sum_{i=0}^{N}\binom{i+p}{i} = \binom{N+p+1}{N} would be to realise that \binom{i+p}{i} is number of ways to reach cell numbered (i,p) beginning from (0,0) when you can only more down or right*.
Now, what we need is sum of number of ways to reach cells (0,p), (1,p) ... (N,p), which is equivalent to number of ways to reach cell (N,p+1) which is \binom{N+p+1}{N}. Visualise it this way:
![img][123]
Now, each path that reaches violet cell passes through green cells and then there is a unique way to reach violet cell from the green cell. So, we can say number of ways to reach violet cell is sum of number of ways to reach green cells.
[123]: http://www.sumoware.com/images/temp/xzjkqnhencanllac.png
I used the concept of fermat from here(accepted answer on this page), still it showed TLE for the last subtask. This is the link to my solution. Please answer what optimization do i need to perform here? Or is it the case that this approach is slower in particular compared with Lucas(the one explained in the editorial)? If that’s the case, what’s the reason of it being slow as i’m unable to see any?
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.
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) ?
^ As he said, the extra person is a dummy. That is to say, the first n people will get some c (say) <= k things, the remaining (k - c) will go to the last person. There will be a case where the last guy gets everything, so we do -1 to get the right answer.
