can anyone tell me how does the probability in last cast when both are 0 becomes m-1/(2*m)?? i have seen a code having this
if(!a[i] && !b[i]) { v.push_back(make_pair((((m-1)%M)*num)%M, (den*((2*m)%M))%M) ); den = (den*(m%M))%M; } somebody plz me how is the probability calculated in this case?
You independently select two numbers uniformly at random from {1, 2, ..., m}. The probability they are equal is 1 / m, since after you select the first you have a 1 / m chance of selecting the same value for the second.
So the probability they are different is 1 - 1 / m = (m - 1) / m. In the case they are different by symmetry it is equally likely that the first is larger than the second and that the second is larger than the first. So the probability the first is larger than the second becomes (m - 1) / 2m.
The characters at
A[i]
andB[i]
must be different. (withA[i] > B[i]
)There are choose
(m, 2) = m(m - 1)/2
ways of choosing two different characters.How many ways are there to choose two characters in general ?
m x m = m^2
Probability = Number of ways of choosing different characters/ Number of ways of choosing characters
=
(m(m - 1)/2) / m^2 = (m - 1)/2m
This is my implementation. It may be useful for you.