Supermean

[temper_3243]

I wrote 2 for loops. I was getting TLE.
i made up the formula as (a+nc1*b + nc2*c + nc3*d.......+ nc1*m + n)/2^n-1

For n=50000, we have 50000 C 20000 . How are we going to find such a big number.

How do you solve the problem supermean ?

[Cho]

There is a minor mistake in your formula: It's n in the nCr but n-1 in 2^(n-1).

50000C25000 is extremely large. But 50000C25000/2^50000 is not. Meanwhile, nCr/2^n is small enough to ignore it for r close to 0 or n. I used a single for-loop to compute your formula. Use a double to store nCr/2^n. However, nC0/2^n is smaller than the smallest value of double, so don't divde the nCr by 2^n when r is small. As r increases, nCr becomes larger, divide it by power of 2 gradually. When r is close enough to n/2, you can use the nCr/2^n to compute the weighted sum.

(I know the above english description is terribly poor. Sorry.)