viii. Digit DP

Count (or sum, or optimise) over integers in $[L,R]$ (up to $10^{18}$ or given as strings of $10^5$ digits) satisfying a property computed digit by digit. Answer $f(R)-f(L-1)$ where $f(N)$ handles $[0,N]$. Build the number from the most significant digit with a tight flag (prefix equals $N$‘s prefix so far), a started flag when leading zeros matter, and whatever small state the property needs.

Template

Memoise only non-tight states and index them by the number of remaining digits: then the table does not depend on $N$ and is reused across all queries and test cases.

int K; ll memo[20][200]; bool vis[20][200]; string s;     // property: digit sum divisible by K
ll go(int pos, int rem, bool tight) {
    if (pos == sz(s)) return rem == 0;
    int left = sz(s) - pos;
    if (!tight && vis[left][rem]) return memo[left][rem];
    ll r = 0; int hi = tight ? s[pos] - '0' : 9;
    for (int d = 0; d <= hi; d++) r += go(pos + 1, (rem + d) % K, tight && d == hi);
    if (!tight) vis[left][rem] = 1, memo[left][rem] = r;
    return r;
}
ll countUpTo(ll N) { if (N < 0) return 0; s = to_string(N); return go(0, 0, true); }   // counts x in [0, N]

Proof: tight flag, reuse, and $f(R)-f(L-1)$

A number $x\le N$ with the same length (pad with leading zeros) is characterised by the first position where its digit is smaller than $N$‘s, or by being equal to $N$. While tight, the next digit can’t exceed $N$‘s digit; choosing a smaller one makes every later digit free; this enumerates each $x\in [0,N]$ exactly once. A non-tight state’s count depends only on the remaining length and the property state, not on $N$, so memoising by (digits left, state) is valid across different bounds. Finally $[L,R]=[0,R]\setminus [0,L-1]$.

The extra state

Property	State
digit sum $=S$ / divisible by $K$	running sum (at most $9\cdot 18$ distinct values for 18-digit numbers) or remainder
number divisible by $K$	$x\mathrm{mod}K$ (append digit: $10r+d$)
divisible by its own digit sum	loop over target sum $t\le 9\cdot 18$; state (sum, $x\mathrm{mod}t$)
no two equal adjacent digits, monotone digits	previous digit (+ started)
all digits distinct / digit multiset conditions	10-bit mask, or counts
avoid/contain substrings from a set	Aho–Corasick state (Aho–Corasick)
number of nonzero digits $\le k$	counter
palindromes in $[0,N]$	fix the first half and compare the mirrored number with $N$
lucky (divisible by each nonzero digit)	$x\mathrm{mod}2520$ and the lcm of digits so far (48 divisors of 2520)

Sums instead of counts: return (count, sum) and combine $\text{sum}+=d\cdot 10^{\text{left}-1}\cdot {\text{cnt}}_{\text{child}}+{\text{sum}}_{\text{child}}$. Sums of squares or of $f(x)$ follow by carrying the needed power sums.

$k$-th number with the property: $\text{countUpTo}$ is monotone, so binary search on $N$ ($\times 60$ digit DPs), or descend directly: at each position, try digits in increasing order, subtracting the number of completions of each free suffix until the $k$-th falls inside one.

Several numbers at once

Process bits (or digits) of all numbers together, with one tight flag per bound. Lower bounds get their own flag (“still equal to $L$‘s prefix”).

ll pairsDisjoint(ll A, ll B) {                             // # (a, b), 0 <= a <= A, 0 <= b <= B, a & b == 0
    ll dp[2][2] = {{0, 0}, {0, 1}};                         // dp[tightA][tightB]
    for (int bit = 61; bit >= 0; bit--) {
        ll nd[2][2] = {}; int ab = A >> bit & 1, bb = B >> bit & 1;
        for (int ta = 0; ta < 2; ta++) for (int tb = 0; tb < 2; tb++) if (dp[ta][tb])
            for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) {
                if ((x & y) || (ta && x > ab) || (tb && y > bb)) continue;
                nd[ta && x == ab][tb && y == bb] += dp[ta][tb];
            }
        memcpy(dp, nd, sizeof dp);
    }
    return dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1];
}

Typical: pairs with $a\oplus b\le C$ or $a+b=a\oplus b$, $a\le A$, $b\le B$, maximum of $a\oplus b$ over ranges, ”$x$ and $x+k$ both satisfy P”.

Addition with carries: process from the least significant digit with a carry state, e.g. count $x\le N$ such that $x+c$ has digit sum $s$; or verify $a+b=c$ digit-wise for cryptarithm-like problems. When both a carry (LSB first) and a bound (MSB first) are needed, either process LSB first and replace “tight” by a three-way comparison flag (less/equal/greater than $N$‘s suffix), or process MSB first with a “carry expected from below” guess.

Proof: LSB-first comparison flag

Process digits from the least significant end, keeping $c\in \{<,=,>\}$ = comparison of the suffix built so far against the same suffix of $N$. Prepending a digit $d$ against $N$‘s digit $e$ gives: if $d<e$ then $<$, if $d>e$ then $>$, else keep $c$. This is exactly lexicographic comparison read from the most significant digit, since the most significant differing digit decides. At the end, $x\le N$ iff the flag is $<$ or $=$.

Practical notes

• Digit DP on decimal strings of length $10^5$ is fine as long as the state is small; iterate instead of recursing.
• With leading zeros, properties about “the digits of $x$” need started; sums and remainders usually don’t.
• Base $b$ or binary: same template. For bitwise problems, digit DP over bits is often combined with a binary trie view.
• For ”$x$ in $[L,R]$” with two flags (tight-low, tight-high) you avoid the subtraction, which helps when the answer is a min/max rather than a count.