Hello friends can someone help with the math behind this problem ?? @vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299
Thanks in advance 
Guys can someone help with the above question ?? What concept of maths is involved here ?? Guys just some hint will also be helpful
According to the editorial on Hackerearth, the answer is given by
\frac{(2 \cdot (n + 1)) ^ m \cdot (n + 1 - m)}{n + 1}
First assume there is an (n + 1)^{th} seat between first and last so the seating is circular.
Now 2 \cdot (n + 1) is the number of ways each person can be assigned a seat and entry point. So (2 \cdot (n + 1)) ^ m is number of ways to assign seat and entry point to all m people. Here the entry point functions as only the direction in which a person checks for empty seats. Also note that the (n + 1) ^{th} seat cannot actually be assigned to anyone, but this situation will be eliminated from the final answer.
The seating is circular, so each person is guaranteed to find a seat. But if the (n + 1)^{th} is full, that means at some point a person could not find a seat in the original problem and became angry. Now we need to count the number of ways in which this seat remains empty.
For each way exactly n + 1 - m seats remain empty. By intuition I can claim that each of the \binom{n + 1}{n + 1 - m} choices of seats are equally likely to remain empty. What I want to find is the number of ways where a particular seat is always empty, which is \binom{n}{n - m}.
Now \binom{n}{n - m} = \frac{n + 1 - m}{n + 1}\binom{n + 1}{n + 1 - m}, so the answer is
\frac{n + 1 - m}{n + 1} \cdot (2 \cdot (n + 1)) ^ m
2 Likes
Got it know. Thankyou so much for this
Got it now . Python’s pow is too slow . Self made power function in C++ does it in one go
Actually it is not Python’s fault, you forgot to provide the modulo argument to the power function. You need to call it as pow(2*(n+1),m,mod). Also you cannot directly divide under a modulo, you need to multiply with the modular inverse instead. Or in this case, that can be avoided by cancelling one (n + 1) term from numerator and denominator.
Oh my bad ;0