To solve this problem, we need to determine the number of integers between two given integers (a) and (b) (inclusive) whose sum of digits is even. Given the potential size of (a) and (b) (up to (10^{18})), an efficient approach using digit dynamic programming (digit DP) is necessary.

Approach

1. Digit DP Insight: The key idea is to compute the number of valid numbers (with even digit sum) from 0 to (n) using digit DP. We then find the result as the difference between the count of valid numbers from 0 to (b) and the count from 0 to (a-1).
2. DP State: We use a recursive DP function with memoization to track:
   • Current digit position.
   • Parity of the sum of digits so far (0 for even, 1 for odd).
   • Whether the current number being formed is still tight (i.e., matches the prefix of (n) up to the current position).
3. Transition: For each digit position, we consider all possible digits (0 to 9, or up to the current digit in (n) if tight). We update the parity and tightness for the next position.

Solution Code

def count_even(n):
    if n < 0:
        return 0
    s = str(n)
    digits = list(map(int, s))
    n_digits = len(digits)

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, sum_parity, tight):
        if pos == n_digits:
            return 1 if sum_parity == 0 else 0
        max_d = digits[pos] if tight else 9
        total = 0
        for d in range(0, max_d + 1):
            new_tight = tight and (d == max_d)
            new_parity = (sum_parity + d) % 2
            total += dp(pos + 1, new_parity, new_tight)
        return total

    return dp(0, 0, True)

# Read input
a, b = map(int, input().split())

# Compute result
result = count_even(b) - count_even(a - 1)
print(result)

Explanation

1. count_even Function: This function calculates the number of integers from 0 to (n) with even digit sum. It uses memoization to avoid redundant calculations.
   • Base Case: When all digits are processed (pos equals the length of the digit string), return 1 if the sum parity is even, else 0.
   • Transition: For each digit position, iterate over possible digits, update the parity and tightness, and accumulate the count of valid numbers.
2. Result Calculation: The result is obtained by subtracting the count of valid numbers from 0 to (a-1) from the count from 0 to (b). This gives the number of valid numbers between (a) and (b).

This approach efficiently handles large values of (a) and (b) by leveraging digit DP, ensuring the solution runs in time proportional to the number of digits (up to 18 for (10^{18})) and the state space (18 positions × 2 parity values × 2 tightness values = 72 states). This makes the solution both optimal and scalable.

作者声明:本文包含人工智能生成内容。