Digit Dynamic Programming: Efficiently Counting Integers with Specific Digit Features in a Range

Core Logic and Mathematical Principles

The essence of Digit Dynamic Programming (Digit DP) is optimizing topological counting using a Trie-like structure for large integer sets expanded digit by digit. It is mainly used to solve problems such as "counting the number of integers in the range $[L, R]$ that satisfy certain specific digit features (such as not containing specific digits, or the sum of the digits being prime, etc.)".

1. Dimensional Reduction via Interval Difference: Maintaining complex digit constraints directly on the closed interval $[L, R]$ is extremely difficult. Since the counting function $f(X)$ (which represents the count of integers satisfying the condition within $[0, X]$) has explicit additivity and independence, the problem can be losslessly reduced to two independent single-boundary counts via prefix differences:

$$\text{Ans} = f(R) - f(L - 1)$$

2. Trie Tree Structure of State Space and Memoization Pruning: For a given upper bound $X$, we can view the selection process from the most significant to the least significant digit as a topological traversal on a high-dimensional digital trie (Trie tree).

• Edge Constraint (Limit): If the previous digits are tightly bound to the corresponding digits of $X$, then the upper limit of the current digit's choices is constrained. For example, if $X = 324$, and the first two digits are chosen as 3 and 2, the current digit can only choose up to 4; if the first two digits are 3 and 1, the current digit can choose freely from 0 to 9.
• Geometric Nature of State Overlap: Once a decision at a certain digit "breaks away from the edge constraint" (i.e., the current chosen digit is strictly less than the corresponding digit of $X$), all subsequent lower digits will no longer be constrained by the upper bound $X$ when choosing from 0 to 9. At this point, the topological structure of the subsequent search subtree is completely equivalent and overlapping. By introducing a memoization array to record the general state after breaking the constraint, exponential brute force can be pruned to a highly regular complexity of $O(\text{len} \times \text{states})$.

State Design and Algorithm Derivation

The most elegant and least prone to failure implementation of Digit DP is a highly cohesive memoization search template.

1. Core Search Function Parameter Design

Define int dfs(int pos, int state, bool limit, bool lead):

• pos: The current digit pointer (advancing from the most significant to the least significant).
• state: The feature state required by the problem (such as the previous digit, the sum of the digits already chosen, etc.).
• limit: A boolean flag indicating whether the current digit is constrained by the upper bound $X$.
• lead: A boolean flag indicating whether all previous digits were leading zeros.

2. State Transition and Memoization Control

Let the upper limit of the current digit corresponding to $X$ be $up$ (if limit is true, then $up = \text{digits}[pos]$, otherwise $up = 9$). By looping through the digits that can be filled in the current position $i \in [0, up]$:

• The next limit state is next_limit = limit && (i == up).
• The next leading zero flag is next_lead = lead && (i == 0).
• Accumulate the return value of the sub-state: res += dfs(pos - 1, update(state, i), next_limit, next_lead).

3. Mathematical Criteria for Memoization Backtracking

The return value of dfs(pos, state) can only be written into the memoization array dp[pos][state] when limit == false and lead == false. Because once there is an edge constraint or leading zero contamination, the value calculated at that moment is just an incomplete subtree and cannot be reused as a general state.

C++ Standard Source Code (NOIP Style)

The following code solves the classic Digit DP model: "Count the number of integers in the range $[L, R]$ that do not contain consecutive identical digits (i.e., adjacent digits are different)", strictly compatible with the Linux g++ -O2 compilation standard.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

long long dp[20][11]; // dp[pos][pre_digit] Memoization array
int digits[20];       // Stores each digit of the upper bound X after decomposition

// Core memoization search function
long long dfs(int pos, int pre, bool limit, bool lead) {
    // Base condition: all digits processed, indicating a valid number has been successfully constructed
    if (pos == 0) {
        return 1; 
    }

    // Critical pitfall: only when there are no constraints and no leading zero contamination can we directly read the memoization cache
    if (!limit && !lead && dp[pos][pre] != -1) {
        return dp[pos][pre];
    }

    // Dynamically lock the upper limit of the current position based on the edge state
    int up = limit ? digits[pos] : 9;
    long long res = 0;

    for (int i = 0; i <= up; ++i) {
        // Condition filtering: if not in leading zero state, the current digit cannot be the same as the previous digit
        if (!lead && i == pre) {
            continue;
        }

        // Recursively enter the next digit
        // 1. The new limit state is determined by the current limit and whether it fills the upper limit digit
        // 2. The new lead state is determined by the current lead and whether the current digit continues to fill 0
        res += dfs(pos - 1, i, limit && (i == up), lead && (i == 0));
    }

    // Critical pitfall: only when there are no constraints and no leading zero contamination can we solidify the current value into the global cache
    if (!limit && !lead) {
        dp[pos][pre] = res;
    }

    return res;
}

// Solve the number of valid quantities in the range [0, n]
long long solve(long long n) {
    if (n < 0) return 0;
    if (n == 0) return 1;

    int len = 0;
    while (n > 0) {
        digits[++len] = n % 10; // Decomposing the number, digits[1] is the least significant, digits[len] is the most significant
        n /= 10;
    }

    // Before each solution, the memoization array must be reset to -1
    memset(dp, -1, sizeof(dp));

    // Start from the most significant digit downwards, initial state: constrained by edge (true), leading zero (true), previous digit passed an irrelevant value 10
    return dfs(len, 10, true, true);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long l, r;
    if (cin >> l >> r) {
        // Use prefix differences to achieve lossless mapping of the closed interval [L, R]
        cout << solve(r) - solve(l - 1) << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

1. Incorrectly reading and writing memoization for states with edge constraints (limit == true)

• Phenomenon: At the beginning of the dfs function, unconditionally wrote if (dp[pos][state] != -1) return dp[pos][state];. This would lead to serious counting omissions. Because the number of solutions found when constrained by the edge is a truncated value forced by the upper bound. Once this incomplete value is cached as a general template, when later in an unconstrained state reaching the same pos and state, it will directly return this smaller value, causing the final answer to shrink severely.
• Avoidance Strategy: Remember the iron law of Digit DP: only when !limit and !lead hold can the dp array be read and written.

2. Ignoring the difference boundary $L-1$ leading to integer underflow

• Phenomenon: When the input data has $L = 0$, calling solve(l - 1) will pass -1. If there is no special judgment at the entrance of the solve function with if (n < 0) return 0;, the code will attempt to decompose a negative number, causing the entire digit separation logic to enter a dead loop or produce out-of-bounds dirty data.
• Avoidance Strategy: Conduct strict safety checks on the left boundary of the prefix difference. Either directly return $f(R)$ when $L=0$, or safely cut off negative inputs within the solve function.

Classic NOIP/Luogu Real Questions

1. Luogu P2602 [ZJOI2010] Digit Counting

• Problem Description: Given two positive integers $a$ and $b$, count how many times each digit ($0 \sim 9$) appears in all integers within $[a, b]$. $a, b \le 10^{12}$.
• Essence of the Problem and Solution Idea: A digit counting problem that requires maintaining multiple states concurrently. Since we need to count the specific frequency of digits, the state dimension needs to be expanded.
• Core Idea: The outer layer enumerates the current digit $X$ from $0$ to $9$. For digit $X$, design dfs(pos, count, limit, lead), where count records how many $X$ have been filled from the most significant to the current position. When reaching pos == 0, directly return count as the contribution of this branch to the total frequency. For digit $0$, it must strictly cooperate with the lead flag, only when lead == false can the filled 0 be counted as a valid digit, and 0 in the leading zero state must not be counted into count.

2. Luogu P4999 Annoying Math Homework

• Problem Description: Given the interval $[L, R]$, calculate the total sum of the digits at each digit position of all integers within the interval. Since the answer can be large, the result needs to be taken modulo $10^9+7$. Multiple data sets, $L, R \le 10^{18}$.
• Essence of the Problem and Solution Idea: Standard cumulative sum mapping of digits.
• Core Idea: The cumulative sum of digits conforms to the topological structure of Digit DP. The state is designed as dfs(pos, sum, limit, lead), where sum represents the sum of digits already filled in the high position. When enumerating the current position to fill digit $i$, the next layer's state value is directly updated to sum + i. Upon reaching the leaf node pos == 0, directly return sum. Since there are multiple data sets and $R$ reaches $10^{18}$, the size of the memoization array is set to dp[20][200] (the maximum digit sum is $18 \times 9 = 162$), and the same unpolluted dp array can be used for each data set to achieve rapid results.