Hopscotch
This problem asks us how many different (integral) paths we can take between two XY pairs given each step must progress at least T towards the destination in EACH cardinal direction (aka, must move at least T towards the destination in the X direction, and T towards the destination in the Y).
The bounds are 1 million.
A "standard" DP solution would involve iterating over all valid jumps and adding the number of ways to get to OUR cell to the NEXT cell. This results in a DP grid of 10^6^2, and each relation takes another 10^6^2 to run...and of course 10^24 is much too slow.
As is common with many problems which have explicit rules for X and Y directions, we should consider solving it independently in each dimension, and then combining them. Lets focus on the "combine" step first. In order to combine the problem in two dimensions, we know that the path in each dimension has the same number of steps (since the final steps must each move in both dimensions). This reduces to "how many ways can I cover D distance in N steps (in one dimension) with minimum size T". If we could come up with a solution to that problem, we could combine the two dimensions by multiplying. If I have x ways to get there in X dimension, and y ways in Y, each with some n steps, I know there are x*y combinations of the two.
So now the tricky part, "how many ways can I cover D distance in N steps with minimum size T." We can simplify this problem by eliminating the minimum T constraint. Since we know we are taking exactly N steps, by default, N*T distance will be covered just by the minimum. If we then subtract that from D, we are just looking for the number of partitions of size N with no minimum. To make this slightly cleaner, we can instead subtract (N-1)*T, and then our minimum integer becomes 1...which becomes convenient. We can imagine the number of such partitions is the number of distinct ways we can place N-1 "dividers" in a range of (D-(N-1)*T) elements. Given the number of elements, there are (D-(N-1)*T) -1 places to put the N-1 dividers, meaning the total number of unique partitions is (D-(N-1)*T)-1 CHOOSE N-1.
This result is a direct application of Stars and Bars Theorem. Check out the wiki page to visualize how it works. In this case, we have the D-(N-1)*T "stars" and N-1 bars, and need to ensure that each partition has at least 1 in it.
One thing remains. The standard ways to compute NCR are
- n^2 DP solution (too slow)
- multiply-divide solution (multiply biggest number in numerator, divide smallest number in denominator...repeat)....also too slow
So what to do? Normally the second solution is used to prevent the nominator from growing too large. But remember we are doing mod of some big prime! So we can just precompute x!%p up to 10^6, and then just evaluate the NCR directly when needed.