VECTAR12 - Garden of Mangu
Mangu bought a new garden for himself. The garden is shown below in the image. The garden is semi infinite i.e. infinite in two directions (+x direction and +y direction). Garden's square cells are indexed as in the diagram. Changu comes to visit Mangu and see his garden. He is standing initially on (0, 0). From a particular cell he can travel in 8 directions if possible. His task is to go from (0, 0) to (n, k) in n steps. Your task is to calculate the number of possible paths he can take.
Input
The first line contains the number of test cases, T. The next T lines contain two integers n and k separated by a single space.
Output
You have to print the number of possible paths modulus 1000000007.
Example
Input: 2 1 1 2 0 Output: 1 2
Explanation
The possible paths for two case are shown below:
Case 1:
Case 2:
Constraints:
T<10^5
0<=N<7000
0<=K<=N
hide comments
|
Rafail Loizou:
2021-05-10 19:01:25
@dwij28 I think that it was done by purely using math rather than DP. I tried implementing such solution but the thing is I don't know if the array of the multiplicative inverses from 0 to 7000 would fit in the 50K bytes limit that the code has and also allow me to code the solution. Because if you have the multiplicative inverses ready then it becomes a linear solution. I did a rough estimate as to how many characters it would need which is 7000 * 10 so 70K bytes of code, thus I was discouraged from trying such a solution. Also the computation of such an array would take a lot of time.
|
|
ks1999:
2016-10-08 12:14:26
ez dp Last edit: 2020-04-18 18:37:21 |
|
dwij28:
2016-10-07 00:38:47
Got a few TLE's, a few WA (maybe due to case (0, 0)) but got AC in the end (2.88 seconds). :) By the way, the top ranked solution by @Min_25 is 0.06 seconds & 4M of memory. Just brilliant. I have no clue how to optimize the solution to that extent. Hats off to the genius @Min_25. |
|
Min_25:
2016-07-17 11:05:12
When the problem has some images, please upload them to http://www.spoj.com/uploads/.
|
|
icm2015007:
2016-07-15 19:14:24
AC! Last edit: 2016-07-20 20:28:50 |
|
Piyush Kumar:
2016-07-14 12:37:28
Please mention anything that is not clear from the problem statement. |
| Added by: | Piyush Kumar |
| Date: | 2016-07-14 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
| Resource: | Own Problem |
RSS