Overview

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

Since \(N\) can be as large as \(10^{18}\), we cannot search all integers from \(1\) to \(N\). Instead, we use digit DP to count them.

Analysis

The total difference (which we will refer to as the “fluctuation value”) of an integer can be calculated by looking only at adjacent digits.

For example, for \(3517\):

\[ |3-5| + |5-1| + |1-7| = 12 \]

In other words, when deciding the digits from left to right, the increase in the fluctuation value caused by the next digit depends only on the “difference from the immediately preceding digit”.

Therefore, it is sufficient to maintain the following information:

• Whether we are currently matching the prefix of \(N\)
• Whether the number has already started (i.e., we have placed a non-zero digit)
• What the immediately preceding digit is
• What the sum of the fluctuation value up to this point is

A naive search through all integers from \(1\) to \(N\) would be far too slow, since \(N\) can be up to \(10^{18}\).

Instead, we construct integers less than or equal to \(N\) “digit by digit” to count the valid numbers efficiently. This is known as Digit DP.

We also need to handle numbers with fewer digits than \(N\).

For example, if \(N=500\), numbers like \(7\) and \(42\) are also valid candidates. In Digit DP, we can represent them with leading zeros as:

\[ 007,\ 042 \]

However, since leading zeros are not part of the actual number, they should not be included in the fluctuation value calculation. To handle this, we maintain a state indicating “whether the number has already started”.

Algorithm

We receive \(N\) as a string and process the digits from the most significant to the least significant.

We define the DP state as follows:

\[ dp[tight][started][prev][sum] \]

This represents the number of ways to form a prefix such that, for the digits processed so far:

• \(tight\) : If the digits processed so far match the prefix of \(N\), this is \(1\); if the formed prefix is already strictly smaller than \(N\), this is \(0\).
• \(started\) : If we have already placed at least one non-zero digit, this is \(1\); otherwise, it is \(0\).
• \(prev\) : The actual digit placed immediately before.
• \(sum\) : The sum of the fluctuation value so far.

Note that if the number has not started yet, there is no preceding digit. We use prev = 10 as a sentinel value in this case.

The initial state is:

\[ dp[1][0][10][0] = 1 \]

This means we have not placed any digits yet (so it matches \(N\)’s prefix, the number has not started, and the fluctuation value is \(0\)).

At each step, we try placing the next digit dig.

If the current state has tight = 1, the maximum digit we can place is the corresponding digit of \(N\).

If the current state has tight = 0, it is already guaranteed to be smaller than \(N\), so we can freely place any digit from \(0\) to \(9\).

The transitions are as follows:

Case 1: The number has not started yet

When started = 0, if we choose dig = 0, the number still does not start.

In this case, the fluctuation value does not increase.

ndp[ntight][0][10][sum] += cur;

On the other hand, if we choose dig > 0, this becomes the first digit of the number.

Since there is no adjacent digit for the very first digit, the fluctuation value does not increase.

ndp[ntight][1][dig][sum] += cur;

Case 2: The number has already started

When started = 1, the fluctuation value increases based on the difference between the preceding digit and the next digit dig.

The amount of increase is:

\[ |prev - dig| \]

Therefore, we compute the new sum as:

\[ nsum = sum + |prev - dig| \]

and transition only when \(nsum \leq K\).

int nsum = sum + abs(prev - dig);
if (nsum <= K) {
    ndp[ntight][1][dig][nsum] += cur;
}

Finally, after processing all digits, we sum up:

\[ dp[tight][1][prev][K] \]

By only counting states where started = 1, we exclude the number \(0\). This is necessary because the problem asks us to count integers in the range \([1, N]\).

Complexity

Let \(L\) be the number of digits in \(N\).

Since \(N \leq 10^{18}\), we have \(L \leq 19\).

The number of DP states is determined by:

• \(tight\): \(2\) states
• \(started\): \(2\) states
• \(prev\): \(11\) states
• \(sum\): at most \(K+1\) states

From each state, we transition by trying the next digit from \(0\) to \(9\). Thus, the complexity is as follows:

• Time Complexity: \(O(L \cdot 2 \cdot 2 \cdot 11 \cdot K \cdot 10) = O(LK)\)
• Space Complexity: \(O(2 \cdot 2 \cdot 11 \cdot K) = O(K)\)

Implementation Details

Pay attention to how tight is updated.

If the current state has tight = 1 and the chosen digit is equal to the corresponding digit of \(N\), the next state remains tight = 1.

Otherwise, the prefix is guaranteed to be strictly smaller than \(N\), so the next state becomes tight = 0.

int lim = tight ? limit_digit : 9;
int ntight = tight && (dig == lim);

Additionally, we use started to avoid including leading zeros in the fluctuation value.

For example, 007 is actually the number \(7\), so its fluctuation value should be \(0\). We must not add the difference between the leading 0 and 7.

Therefore, if we choose dig = 0 when started = 0, we do not update the preceding digit and do not increase the fluctuation value.

if (!started && dig == 0) {
    ndp[ntight][0][10][sum] += cur;
}

On the other hand, when we place a non-zero digit for the first time, there was no preceding digit, so the fluctuation value does not increase either.

else if (!started) {
    ndp[ntight][1][dig][sum] += cur;
}

Finally, by adding only the states where started = 1 to the answer, we avoid counting \(0\).

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    int K;
    cin >> N >> K;

    int len = (int)N.size();

    using int64 = long long;

    static int64 dp[2][2][11][154];
    dp[1][0][10][0] = 1;

    for (int pos = 0; pos < len; pos++) {
        static int64 ndp[2][2][11][154];
        memset(ndp, 0, sizeof(ndp));

        int limit_digit = N[pos] - '0';

        for (int tight = 0; tight <= 1; tight++) {
            for (int started = 0; started <= 1; started++) {
                for (int prev = 0; prev <= 10; prev++) {
                    for (int sum = 0; sum <= K; sum++) {
                        int64 cur = dp[tight][started][prev][sum];
                        if (cur == 0) continue;

                        int lim = tight ? limit_digit : 9;
                        for (int dig = 0; dig <= lim; dig++) {
                            int ntight = tight && (dig == lim);
                            if (!started && dig == 0) {
                                ndp[ntight][0][10][sum] += cur;
                            } else if (!started) {
                                ndp[ntight][1][dig][sum] += cur;
                            } else {
                                int nsum = sum + abs(prev - dig);
                                if (nsum <= K) {
                                    ndp[ntight][1][dig][nsum] += cur;
                                }
                            }
                        }
                    }
                }
            }
        }

        memcpy(dp, ndp, sizeof(dp));
    }

    int64 ans = 0;
    for (int tight = 0; tight <= 1; tight++) {
        for (int prev = 0; prev <= 9; prev++) {
            ans += dp[tight][1][prev][K];
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.