Overview

This problem asks us to find the number of integers between \(1\) and \(N\) (inclusive) such that the sum of the absolute differences between adjacent digits (the “fluctuation value”) is exactly \(K\).

Analysis

Since \(N\) can be as large as \(10^{18}\), a naive approach that checks all integers from \(1\) to \(N\) one by one will exceed the time limit (resulting in TLE).

When \(N\) is extremely large in problems that ask us to “count the number of integers from \(1\) to \(N\) satisfying certain conditions”, Digit DP is a highly effective technique. In Digit DP, we determine the digits one by one from the most significant digit to the least significant, counting the ways while keeping track of the conditions (such as the fluctuation value) up to the current digit.

To calculate the fluctuation value, we need to know the “digit of the previous position”. Additionally, when filling digits from top to bottom, keeping track of “whether the number constructed so far matches the prefix of \(N\) exactly” allows us to ensure the constructed number does not exceed \(N\). We also need to manage leading zeros (for example, a flag to prevent treating 3517 as 03517, which would incorrectly introduce a fluctuation between 0 and 3).

Algorithm

We solve this problem using Digit DP. We maintain the following four elements in our DP state:

• j: the fluctuation value accumulated so far (between \(0\) and \(K\))
• p: the digit of the previous position (\(0\) to \(9\))
• t: whether the constructed prefix is currently tight against the upper bound \(N\) (1: tight/matching, 0: strictly less than)
• z: whether the number has not started yet (i.e., we are still placing leading zeros) (1: not started yet, 0: already started)

As the initial state, we set dp[0][0][1][1] = 1, representing the state before choosing any digits. We transition by choosing a digit \(d\) (\(0\) to \(9\)) from the most significant digit to the least significant digit. The upper limit for \(d\) is the corresponding digit of \(N\) if t == 1, and \(9\) if t == 0.

The fluctuation value at transition is calculated as follows: - When z == 1 and \(d == 0\): Since the number has not started yet, the fluctuation value remains unchanged (j does not change), and z remains 1. - When z == 1 and \(d > 0\): Since the first non-zero digit has appeared, the fluctuation value remains unchanged (j does not change), p becomes \(d\), and z becomes 0. - When z == 0: We add \(|p - d|\) to the fluctuation value and set p to \(d\).

If the calculated fluctuation value exceeds \(K\), we prune the transition (do not transition) to avoid redundant calculations.

Finally, the answer is the sum of the states where all digits have been determined, the fluctuation value is exactly \(K\), and the number has started (z == 0). Note that if \(K\) exceeds the maximum possible fluctuation value (\(153\)), we output \(0\) since no such numbers can exist.

Complexity

• Number of states: Number of digits \(L \le 19\), fluctuation value \(K \le 153\), previous digit \(10\), tight flag \(2\), leading zero flag \(2\)
• Time complexity: \(O(L \cdot K \cdot 10 \cdot 2 \cdot 2 \cdot 10) = O(L \cdot K)\) (Although the constant factor is relatively large, it is fast enough since \(L \le 19\) and \(K \le 153\))
• Space complexity: \(O(K \cdot 10 \cdot 2 \cdot 2)\) (Since we only need to keep the DP table of the previous digit)

Key Implementation Points

• Handling leading zeros is crucial. For example, when evaluating the number 7, we must avoid treating it as if it has leading zeros and incorrectly adding \(|0 - 7| = 7\) to the fluctuation value. This is managed using the z (leading zero) flag.

• Since the maximum possible fluctuation value is limited, we can optimize by not updating the state if j + abs(p - d) exceeds \(K\). This reduces the number of transitions and speeds up the execution.

• When transitioning to the next digit, we construct a new DP array (dp_next) based on the DP array of the previous digit (dp_prev) to prevent bugs caused by in-place updates.

  Source Code

import sys

def solve():
    N_str, K_str = sys.stdin.readline().split()
    N_str = N_str.strip()
    K = int(K_str)
    
    if K > 153:
        print(0)
        return

    N_digits = [int(c) for c in N_str]
    L = len(N_digits)

    # dp[j][p][t][z] where j:揺れ値, p:前の桁, t:tight, z:leading_zero
    dp_prev = [[[[0] * 2 for _ in range(2)] for _ in range(10)] for _ in range(K + 1)]
    dp_prev[0][0][1][1] = 1

    for i in range(L):
        N_d = N_digits[i]
        dp_next = [[[[0] * 2 for _ in range(2)] for _ in range(10)] for _ in range(K + 1)]
        for j in range(K + 1):
            for p in range(10):
                for t in range(2):
                    for z in range(2):
                        cur = dp_prev[j][p][t][z]
                        if cur == 0:
                            continue
                        max_d = N_d if t else 9
                        for d in range(max_d + 1):
                            nt = 1 if (t and d == N_d) else 0
                            if z and d == 0:
                                nj = j
                                np = p
                                nz = 1
                            elif z and d > 0:
                                nj = j
                                np = d
                                nz = 0
                            else:
                                nj = j + abs(p - d)
                                np = d
                                nz = 0
                            
                            if nj <= K:
                                dp_next[nj][np][nt][nz] += cur
        dp_prev = dp_next

    ans = 0
    for p in range(10):
        ans += dp_prev[K][p][0][0]
        ans += dp_prev[K][p][1][0]
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.