My approach involved the following ideas:
- We can precalculate the number of ways to stay within a one dimensional segment of a particular length, starting at a particular place, and using a particular number of moves.
- From here, the number of ways to stay within D dimensions of the grid using M moves can be found by going through all possible ways of splitting M into two chunks (say, k and M-k) and interleaving the k moves we use to stay within dimension D (at starting position x_D) with the number of ways to stay within D-1 dimensions using M-k moves.
Of course, there is a trick in counting the number of ways to interleave the moves to stay within 1 dimension with the number of ways to interleave the moves to stay within the remaining D-1 dimensions. ;)
Say for every move in dimension D, we write a 0. For every move in the remaining D-1 dimensions, we write a 1. The number of interleavings is, of course, the same as the number of possible binary strings composed in this fashion. If we have M total moves, k of which are made in dimension D, this gives, of course, M choose k possible interleavings.
But we have to give the output modulo 10^9 + 7! How do we calculate M choose k modulo this number? Fortunately p = 1E9 + 7 is prime, so the group of integers modulo p gives a field. This means that we can simply calculate M choose k (mod p) as M! * (k!)^-1 * ((M-k)!)^-1, all modulo p, of course. Since p is prime we are guaranteed that the numbers k! and (M-k)! have multiplicative inverses. I used the extended Euclidean algorithm to get these, although I believe you could just as well raise them to the p-2 power (which, by Fermat's theorem, gives the multiplicative inverse).
Whew! It's great to see a problem that combines concepts from dynamic programming, discrete math, and number theory!
Hey Stephen!
ReplyDeleteCan you suggest me some problems to practice and some topics to study before i am able to solve this kind of problems..
It will be very helpful.
Thanks
Hi Vish,
DeleteFor this particular kind of problem, I highly recommend taking a look at Project Euler. It has lots of problems on number theory and dynamic programming, and solving them will help you get in the right kind of mindset.
Additionally, you may want to invest in a few texts -- Introduction to Algorithms (CLRS) and an introductory number theory textbook are recommended reading.
Good luck!
-Stephen
Hi Stephen,
ReplyDeleteNice post and explanation.
I didn't quite follow the number theoretic idea though. What I understand is, we have to find out the no. of ways of choosing k things out of M, where 0<=k<=M. This turns out to be:-
Mc0+Mc1+Mc2+.......+McM = pow(2,M).
We need to output pow(2,M) % (10^9 + 7).
Your post talks of computing (M! * inverse(k!) * inverse (M-k)!) % (10^9 + 7). Since <1=M<=300, the factorials are going to be very very long. Is that what you did, or I am not etting this correcly.
Thanks,
Seshan,
ReplyDeleteThe post was actually a little intentionally vague, so congrats on parsing it. :)
To compute factorials mod m, notice that (a*b mod m) == (a mod m) * (b mod m) mod m. So you can mod the product as you go along, and your factorials won't get too big.
Stephen
Hi Stephen,
ReplyDeleteCan you please explain solution of this problem in detail. I had spent 2 days but still struggling with its solution.
Thanks
Oh man, it's been years... I honestly don't remember.
DeleteI think there are two components. The first is figuring out how to count the ways, and the second is figuring out how to count the number of ways 1E9 + 7, which is prime. The first component is harder I think, but ends up just being dynamic programming.
So maybe it's easy if you store an entry for # ways starting from point (x1,x2,...,xD) with k moves remaining, but the trouble is that then you need O(M*\prod_i D_i) memory. So the key is to decompose things by dimension... do the above dp, but for each dimension only. Moving along one dimension does not change the number of ways to move along another one. So you can then do dp based on 1) which dimension you're in and 2) number of moves remaining.
Does that make sense? Basically, we're deciding in advance how many moves to make in each dimension, and for that choice we count the number of ways to stay within the grid. Then sum over all those choices (for how many moves to make in each dimension).