Topper Rama Rao
Link to the question : HLP_RAMS
To find whether nCr is odd or even we use the lucas theorem.
Lucas theorem states that nCr % m, where, m is a prime number = (n0 C r0 % m) * (n1 C r1 % m)*........
(nk C rk % m), where n<0n1...nk and r0r1...rk are the representation of n and r in base m respectively. Hence, in base 2 representation, the digits will be either 0 or 1.
So,according to lucas theorem, nCr % 2 will give us the cases 1C1, 1C0, 0C0, 0C1. Now, 0C1 = 0. Hence, if nCr has the case 0C1 then its always even else odd.
Now for counting the number of odd terms we count the number of 1's in n' s binary representation. We can assign either 0 or 1 to the 1's of n in nCr. Hence, number off odd terms = 2^(no of 1's).
SOURCE CODE :
/* Topper Rama Rao */
/* Sushant Gupta */
long long int n,i,odd,x,c=0;;
odd = pow(2,c);