1. Prefix Reduction $[L, R] \to [0, R] - [0, L-1]$ & The tight Automaton
To count integers $x \in [L, R]$ satisfying a digit predicate $P(x)$, we reduce the two-sided range query to two one-sided queries: $\text{solve}(R) - \text{solve}(L - 1)$ (or $\text{solve}(R) - \text{solve}(L) + P(L)$ when $L$ is a 1000-digit string). Let $S[0..n-1]$ be the base-10 digit string of the upper bound $R$ (most significant digit at index $0$).
Core Invariant — The tight (Prefix-Match) & started (Leading-Zero) Flags
When choosing digit $d$ at position $\text{pos} \in [0..n-1]$:
1. tight Flag (bool): tight == true iff every previous digit $0..\text{pos}-1$ was chosen equal to $S[0..\text{pos}-1]$.
- If tight == true, $d$ is restricted to $0 \le d \le S[\text{pos}]$, and next_tight = (d == S[pos]).
- If tight == false, our prefix is already strictly smaller than $S$'s prefix! Thus $d$ can be any digit $0 \le d \le 9$, and next_tight = false forever.
2. started Flag (bool): Shorter numbers (e.g., $42$ when $R = 5000$) are generated as $0042$. When the problem depends on leading zeros (such as "no adjacent equal digits", where $0042$ has two leading $0$s that are NOT real digits, or "count occurrences of digit $0$"), started == false indicates we are still in the leading-zero prefix, and next_started = started || (d > 0).
2. Cross-Query Memoization Trick: Caching tight == false Across Multiple Test Cases
Observe a powerful structural fact: whenever tight == false, the remaining transitions from (remaining_len, state) depend only on 0..9 and do NOT depend on the input number $R$ at all! Therefore, if you index your memo table by remaining_len = n - 1 - pos and memoize only states where tight == false (and started == true), you can allocate and populate the memo table ONCE globally and answer $Q = 10^5$ range queries $[L_q, R_q]$ without ever clearing memo!
Bound R = '352'"] -->|"d = 3 (Matches R[0])"| T1["pos=1, tight=true
Allowed d in [0..5]"] Root -->|"d in {0, 1, 2} (< R[0])"| F1["pos=1, tight=false
Allowed d in [0..9] (Memoized!)"] T1 -->|"d = 5"| T2["pos=2, tight=true
Allowed d in [0..2]"] T1 -->|"d in [0..4]"| F2["pos=2, tight=false
Shares Memo with F1's children!"] F1 -->|"d in [0..9]"| F2
Hardware Reality — Flat Static Array memo[20][STATE] vs. Clearing on tight == true
For a 64-bit integer $R \le 10^{18}$ ($n \le 19$ digits), at each position pos there is at most one reachable prefix with tight == true (namely, the unique prefix equal to $S[0..\text{pos}-1]$). Thus tight == true states never overlap within a single call! Only tight == false states are reached via multiple paths and benefit from memoization.
3. Complexity Matrix
Trace dimension-by-dimension SOS DP bit-flips F[mask] += F[mask ^ (1<<i)] without overcounting, Broken Profile staircase wavefront domino tiling, and Digit DP tight-prefix automata.
Invariant & State
| Digit DP Problem | Automaton State $\Sigma$ | Digits $D = \log_{10} R$ | Time Complexity | Space Complexity |
|---|---|---|---|---|
| Digit Sum $\equiv 0 \pmod K$ | $\text{rem} \in [0..K-1]$ | O(log_10 R) | O(10 * D * K) | O(D * K) |
| No Adjacent Equal Digits | $\text{last\_d} \in [0..10]$ | O(log_10 R) | O(10 * D * 11) | O(D * 11) |
| Numbers with Distinct Digits | $\text{mask} \in [0..2^{10}-1]$ | O(log_10 R) | O(10 * D * 1024) | O(D * 1024) |
| Avoid Substring Pattern $P$ | KMP Automaton $\text{state} \in [0..|P|]$ | O(log_10 R) | O(10 * D * |P|) | O(D * |P|) |
4. Reference C++20 Implementation
#include <cstring>
#include <string>
#include <vector>
// Count numbers in [0, R] with no two adjacent equal digits (demonstrates both tight and started)
long long count_no_adjacent_equal_digits(long long R) {
if (R < 0) return 0;
if (R == 0) return 1;
std::string s = std::to_string(R);
const int n = static_cast<int>(s.size());
// memo[pos][last_digit][started] for tight == false states (last_digit = 10 means none yet)
long long memo[20][11][2];
std::memset(memo, -1, sizeof(memo));
auto dfs = [&](auto& self, int pos, int last_d, bool tight, bool started) -> long long {
if (pos == n) return 1LL; // Successfully formed a valid number (including 0 if !started)
if (!tight && memo[pos][last_d][started] != -1) {
return memo[pos][last_d][started];
}
int limit = tight ? (s[pos] - '0') : 9;
long long ways = 0;
for (int d = 0; d <= limit; ++d) {
bool next_started = started || (d > 0);
// Adjacent equality constraint only applies once the number has actually started!
if (started && d == last_d) continue;
int next_last = next_started ? d : 10;
bool next_tight = tight && (d == limit);
ways += self(self, pos + 1, next_last, next_tight, next_started);
}
if (!tight) {
memo[pos][last_d][started] = ways;
}
return ways;
};
return dfs(dfs, 0, 10, true, false);
}
long long count_range_no_adjacent_equal(long long L, long long R) {
return count_no_adjacent_equal_digits(R) - count_no_adjacent_equal_digits(L - 1);
}Production Pitfall — Reusing tight == false Memo Across Different-Length Strings Indexed by pos
If you reuse a global memo table across multiple calls $\text{solve}(R)$ and $\text{solve}(L-1)$ where $R$ has $18$ digits and $L-1$ has $12$ digits, indexing memo by left-to-right pos is a fatal bug! pos = 3 in an 18-digit number has $15$ digits remaining, whereas pos = 3 in a 12-digit number has $9$ digits remaining! To share memo across numbers of different lengths, always index by rem_len = n - pos (number of digits remaining to be placed).