0w1

Yuki 589 Counting Even

Problem Description:
Given a non-negative integer N, find the number of i, such that C(N, i) % 2 == 0 and 0 ≤ i ≤ N.

Constraints:
0 ≤ N ≤ 1e18

Solution:
According Lucas's theorem, since we are considering modulo 2, we can observe that i can be any value that is of a subset binary representation of N. Should there be any position where i has its binary value 1 where N doesn't, we will have C(0, 1) = 0, which Lucas's theorem ensures that the result be an even number. However, for any position in N's binary presentation, whether i has it as 0 or 1, given that C(1, 0) = C(1, 1) = 1, it retains the chance to be an odd number.

N = gets.to_i
p N + 1 - 2 ** N.to_s(2).count(?1)