Hello frendz,
Can anyone help me solving this problem. I find some similar solution on the submissions page of this problem but not able to understand any of those solution. Please help.
problem link here
Problem statement : Its Ignus and Timo wants to take part in BreakThrough which is the city wide treasure hunt. As a part of a task in the hunt Timo has to visit some malls in the city.
N malls were situated in a row. Timo has to visit K malls. But as she is running out of time she does not want to visit two consecutive malls.
How many different combinations of malls should Timo consider? Input
The first line contains an integer T — the number of test cases. Next follow T lines, each containing two space separated integers, N and K. Output
For each test case, output a single integer representing the number of combinations of malls.
Output the answer modulo 100003. Constraints
1 ≤ T ≤ 10 1 ≤ N ≤ 10^16 1 ≤ K ≤ 10^16
Sample Input:
Input: 2 5 2 5 3 Output: 6 1
Explanation
For the first test case: vovoo
voovo
vooov
ovovo ovoov oovov For the second test case: vovov where v are the visited malls.
answer
= number of binary strings of length n with k 1's s.t no two 1's are consecutive
So you have n-k 0's placed initially, giving you n-k+1 potential positions for 1's, of which you need to choose k.
So, answer=C(n-k+1,k)
If k > (n + 1) / 2 obviously, the answer is 0. Consider any element of a visited mall and its consecutive unvisitable mall as one. Therefore we have n-2*k elements. Every possible permutation of this is certain to give us a correct solution, but we have k pairs of visited, and n - 2 * k pairs of unvisited malls whose order does not matter. I had no other idea so I tried finding something of a formula. (n - k)! / (n - 2 * k)!(k)! . It may need some fixes in edge cases, (or when n < 2 * k ) but I think this leads to the correct mathematical result.
Let me know if you find any other method :)
UPD: Well, I couldn't see that the answer seems to have been posted.
There has to be exactly k v's and (n-k) o's. And the length of this string has to be exactly n. Let's see how we can model this problem.
At first, let's just place all the o's. So for the first test case where n = 5 and k = 2, we get ooo. Now we need to place k v's between these. How can we do that?
Let's ask this question instead. What can be the possible locations of v's? If we denote the possible locations of v's with X, then for the first test case we get: XoXoXoX. It seems we have (n-k+1) possible locations and we need to place exactly k v's. The number of ways to do this is (n-k+1) choose k or C(n-k+1, k).
Since n and k can be very large and the modulo (a prime) is relatively small, you can use Lucas theorem to efficiently calculate C(n-k+1,k) modulo 100003.