Problem Analysis: D — Xor Sum

This is problem D from AtCoder Beginner Contest 050. The task is to find the number of pairs ( (a, b) ) that satisfy the following conditions:

[ a \oplus b \leq a + b \leq n ]

where ( \oplus ) denotes the bitwise XOR operation, and ( n ) is a given integer.

Thought Process

Key Formula Derivation

The constraint ( a \oplus b \leq a + b \leq n ) can be analyzed as follows: - The value of ( a \oplus b ) is always less than or equal to ( a + b ), as XOR operates on bits without carrying. - Thus, the problem can be reduced to finding pairs ( (a, b) ) such that: [ a + b \leq n ]

To simplify further analysis, we consider all possible combinations of the parity (odd or even) of ( a ) and ( b ), and calculate their contributions separately.

Parity-Based Cases

We represent ( a ) and ( b ) in the forms ( 2a_1 ) or ( 2a_1 + 1 ), distinguishing odd and even numbers:

1. Case 1: Both ( a ) and ( b ) are odd

• Let ( a = 2a_1 + 1 ), ( b = 2b_1 + 1 ).
• XOR result: ( (2a_1 + 1) \oplus (2b_1 + 1) = u ).
• Addition result: ( (2a_1 + 1) + (2b_1 + 1) = v ).
• The condition ( v \leq n ) becomes: [ 2a_1 + 2b_1 + 2 \leq n \implies a_1 + b_1 \leq \frac{n — 2}{2} ]
• Contribution for this case: [ dp\left(\frac{n-2}{2}\right) ]

1. Case 2: Both ( a ) and ( b ) are even

• Let ( a = 2a_1 ), ( b = 2b_1 ).
• XOR result: ( 2a_1 \oplus 2b_1 = u ).
• Addition result: ( 2a_1 + 2b_1 = v ).
• The condition ( v \leq n ) becomes: [ 2a_1 + 2b_1 \leq n \implies a_1 + b_1 \leq \frac{n}{2} ]
• Contribution for this case: [ dp\left(\frac{n}{2}\right) ]

1. Case 3: One odd, one even

• Let ( a = 2a_1 + 1 ), ( b = 2b_1 ) (or vice versa, symmetric case).
• XOR result: ( (2a_1 + 1) \oplus 2b_1 = u ).
• Addition result: ( (2a_1 + 1) + 2b_1 = v ).
• The condition ( v \leq n ) becomes: [ 2a_1 + 2b_1 + 1 \leq n \implies a_1 + b_1 \leq \frac{n-1}{2} ]
• Contribution for this case: [ dp\left(\frac{n-1}{2}\right) ]

State Transition Equation

Combining the results from the three cases, we derive the state transition equation: [ dp[n] = dp\left(\frac{n}{2}\right) + dp\left(\frac{n-1}{2}\right) + dp\left(\frac{n-2}{2}\right) ]

Here, ( dp[x] ) represents the number of valid pairs ( (a, b) ) such that ( a + b \leq x ).

Optimization via Memoization

To avoid redundant calculations, we use memoization. This ensures that each state ( dp[x] ) is only computed once, significantly reducing the time complexity.

Implementation (Pseudo-Code)

Below is the core logic of the solution:

def solve(n):
    # Memoization dictionary
    dp = {}

    def dfs(x):
        # Base cases
        if x < 0:
            return 0
        if x in dp:
            return dp[x]
        
        # Recursive calculation using the state transition formula
        dp[x] = dfs(x // 2) + dfs((x - 1) // 2) + dfs((x - 2) // 2)
        return dp[x]

    # Initialize dp[0] to 1, as there's only one way when n=0 (a=b=0)
    dp[0] = 1
    
    # Compute dp[n]
    return dfs(n)

# Example usage
n = int(input())
print(solve(n))

Summary

1. Problem Modeling: The problem is broken into three cases based on the parity of ( a ) and ( b ).
2. State Transition: Derived a formula combining all cases.
3. Optimization: Applied memoization to improve efficiency.
4. Complexity: Each state is computed only once, leading to a time complexity close to ( O(\log n) ).

This approach effectively addresses both the computational and optimization challenges of the problem.