Zeros and Ones (Codeforces 1734F)
Tags: Math, divide and conquer

Let $$$S$$$ be the Thue-Morse sequence. In other words, $$$S$$$ is the $$$0$$$-indexed binary string with infinite length that can be constructed as follows:   Initially, let $$$S$$$ be "0".  Then, we perform the following operation infinitely many times: concatenate $$$S$$$ with a copy of itself with flipped bits.For example, here are the first four iterations:  Iteration$$$S$$$ before iteration$$$S$$$ before iteration with flipped bitsConcatenated $$$S$$$1010120110011030110100101101001401101001100101100110100110010110$$$\ldots$$$$$$\ldots$$$$$$\ldots$$$$$$\ldots$$$  You are given two positive integers $$$n$$$ and $$$m$$$. Find the number of positions where the strings $$$S_0 S_1 \ldots S_{m-1}$$$ and $$$S_n S_{n + 1} \ldots S_{n + m - 1}$$$ are different. 

Input: Each test contains multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.The first and only line of each test case contains two positive integers, $$$n$$$ and $$$m$$$ respectively ($$$1 \leq n,m \leq 10^{18}$$$).

Output: For each testcase, output a non-negative integer — the Hamming distance between the two required strings.

Note: The string $$$S$$$ is equal to 0110100110010110....In the first test case, $$$S_0$$$ is "0", and $$$S_1$$$ is "1". The Hamming distance between the two strings is $$$1$$$.In the second test case, $$$S_0 S_1 \ldots S_9$$$ is "0110100110", and $$$S_5 S_6 \ldots S_{14}$$$ is "0011001011". The Hamming distance between the two strings is $$$6$$$.

Sample Inputs:
6
1 1
5 10
34 211
73 34
19124639 56348772
12073412269 96221437021

Sample Outputs:
1
6
95
20
28208137
48102976088

Solution (Python):
import random
cache = {}

def popcount(n):
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res

def solve(n, k):
    if k == 0:
        return 0
    if k == 1:
        return popcount(n) & 1
    if k % 2 == 1:
        t = solve(n, k - 1)
        x = popcount(k - 1 ^ n + k - 1) & 1
        return t + x
    if (n, k) in cache:
        return cache[n, k]
    if n % 2 == 0:
        one_cell = 2
        zero_cell = 0
        cnt1 = solve(n // 2, k // 2)
        cnt0 = k // 2 - cnt1
    else:
        one_cell = 0
        zero_cell = 1
        cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
        cnt0 = k - cnt1
    res = one_cell * cnt1 + zero_cell * cnt0
    cache[n, k] = res
    return res
t = int(input())
for _ in range(t):
    cache.clear()
    (n, k) = map(int, input().split())
    print(solve(n, k))

Solution (Python):
import random
cache = {}

def popcount(n):
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res

def solve(n, k):
    if k == 0:
        return 0
    if k == 1:
        return popcount(n) & 1
    if k % 2 == 1:
        t = solve(n, k - 1)
        x = popcount(k - 1 ^ n + k - 1) & 1
        return t + x
    if (n, k) in cache:
        return cache[n, k]
    if n % 2 == 0:
        one_cell = 2
        zero_cell = 0
        cnt1 = solve(n // 2, k // 2)
        cnt0 = k // 2 - cnt1
    else:
        one_cell = 0
        zero_cell = 1
        cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
        cnt0 = k - cnt1
    res = one_cell * cnt1 + zero_cell * cnt0
    cache[n, k] = res
    return res
t = int(input())
for _ in range(t):
    cache.clear()
    (n, k) = map(int, input().split())
    print(solve(n, k))

Solution (Python):
import random
cache = {}

def popcount(n):
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res

def solve(n, k):
    if k == 0:
        return 0
    if k == 1:
        return popcount(n) & 1
    if k % 2 == 1:
        t = solve(n, k - 1)
        x = popcount(k - 1 ^ n + k - 1) & 1
        return t + x
    if (n, k) in cache:
        return cache[n, k]
    if n % 2 == 0:
        one_cell = 2
        zero_cell = 0
        cnt1 = solve(n // 2, k // 2)
        cnt0 = k // 2 - cnt1
    else:
        one_cell = 0
        zero_cell = 1
        cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
        cnt0 = k - cnt1
    res = one_cell * cnt1 + zero_cell * cnt0
    cache[n, k] = res
    return res
t = int(input())
for _ in range(t):
    cache.clear()
    (n, k) = map(int, input().split())
    print(solve(n, k))