Can anyone explain the approach for this problem .
No of ways of dividing an even number n into pairs is \frac{n!}{2^{n/2}\left ( n/2 \right )!}
Firstly store the factorials of all numbers mod 10^9+7 till 10^7 in an array. Then two cases arise
- n is even:
Directly report the answer as product of n!, inverse modulo of 2^n/2 with 10^9+7 and inverse modulo of (n/2)! with 10^9+7.(Take modulo after every product to avoid overflow) - n is odd
Do the above process with n-1 instead of n, and multiply the final answer by n and again take modulo with 10^9+7.
To find inverse modulo you can use Fermatās Principle.
1 Like
That above expression is also equal to the product of all odd integers less than n. So instead of storing factorials, we can store the product of all odd integers less than āiā, in the 'iāth element of an array. This way we donāt have to find the inverse modulo as well.
1 Like
Didnāt simplify the expression and computed directly. Thanks for sharing though.
What should be answer for n=5 ,n=6, n=7 ā¦???
The theory behind the answer: combinatorics - Number of ways you can form pairs with a group of people when certain people cannot be paired with each other. - Mathematics Stack Exchange
Buddy even this helps:
this allows you to calculate n! / (n/2)! relatively easily. You can then divide the answer by 2^(n/2) or take the inverse of the same.
Also, was this rated? If so, then when will these ratings reflect?
This is the first time I used LATEXā¦ I thought that the format will change in outputā¦ Can anyone help?
\dfrac{(2N)!}{{2}^{N} N! }
This is the string you need:
{ \dfrac{(2N)!}{{2}^{N} N! }
1 Like
I donāt really know why but there was a pattern being formed for values of n:
1 1 3 3 15 15 105 105ā¦
So, I simple precalculated all the values and the code was pretty straightforward.
mod = int(1e9)+7
arr = [1, 1]
mul = 3
lim = (10**7)//2+1
for i in range(1, lim):
val = (arr[-1]%mod*mul%mod)%mod
arr.append(val)
arr.append(val)
mul = (mul+2)%mod
for _ in range(int(input().strip())):
n = int(input().strip())
print(arr[n-1])
PS: I know there probably exists a formula to calculate the nth value of the pattern but I was too lazy 
@prayushd bro can you please explain me how you got 15 for n=5 and n=6 and 105 for for 7 and 8 as question was little unclear to me that how its computing magic number
We Can do it using āRecursionā.
@vinayaka05
bro can you please explain me how you got 15 for n=5 and n=6 and 105 for for 7 and 8 as question was little unclear to me that how its computing magic number thatās why i was not able to get right pattern.
Magic number is the number of ways of making all the players play. It there are even number of players, then it is same as the number of possible ways of making pairsā¦which is given by the previously mentioned formula. If the number is odd, then we can choose one player to play with chef in ānā ways and the remaining n-1 people need to be made again into pairs.
The correct formula for making into pairs (only for even n) is (n!)/(pow(2,n/2)*(n/2)!). On simplifying this, we get it as the product of consecutive odd numbers.I canāt see a way to directly prove it.
Hope this helps.
1 Like