Digit DP with Modular Constraints

Intuition, Vocabulary and Foundations

Digit DP builds an integer from left to right while remembering only facts that affect future choices. To count $x\le500$ with $x\equiv2\pmod7$ and digit sum divisible by $3$, append digit $d$ using $r'=(10r+d)\bmod7$ and $s'=(s+d)\bmod3$. Prefixes with identical position, tightness, started flag, residues, and automaton state share the same suffix count.

Leading zeros are padding until started becomes true: they do not enter the digit sum or pattern matcher. The all-padding path represents zero, whose inclusion must be specified explicitly.

A digit-DP state contains exactly the prefix information needed to judge every suffix. Tightness enforces the bound, started separates padding from real digits, and residue and automaton states compress arithmetic and pattern history.

Concept	Example	Boundary	Question answered
Tightness	Matching the bound prefix caps the next digit	After choosing a smaller digit, later digits are free	Which digits are legal?
Leading zeros	`007` represents $7$	Padding zeros should not trigger patterns	Has the number started?
Residue state	$r'=(10r+d)\bmod m$	Storing the full prefix is wasteful	What congruence information survives?
Digit-sum state	Store sum modulo $u$	Exact sum is unnecessary for modular acceptance	What additive state matters?
Automaton	KMP records matched forbidden-prefix length	Last digit alone cannot detect long patterns	What pattern progress matters?
Zero semantics	Count zero only when enabled and accepted	Silent all-padding acceptance causes off-by-one errors	Does zero belong?

Step-by-Step Derivations and Algorithms

For bound digits $b_0\ldots b_{D-1}$, use state $(i,t,z,r,s,q)$: position, tightness, started flag, value residue, sum residue, and automaton state. Choose $0\le d\le b_i$ if tight, otherwise $0\le d\le9$, and set $t'=t\land(d=b_i)$. Padding preserves initial states; a real digit updates residues and the automaton, rejecting forbidden accepting states.

At $i=D$, accept precisely when target states match, with a separate rule for the all-padding zero. Inclusive ranges use $F(H)-F(L-1)$, computing $L-1$ as an integer to avoid decimal-borrow errors.

Digit DP with Modular Constraints algorithm map

flowchart TD
    A[Convert bound to digits] --> B[Choose next legal digit]
    B --> C{Still padding?}
    C -->|Yes| D[Preserve arithmetic and pattern states]
    C -->|No| E[Update residues and automaton]
    E --> F{Forbidden state?}
    F -->|Yes| G[Discard transition]
    F -->|No| H[Memoize suffix state]
    D --> H
    H --> I[Check targets at final position]

Every state counts exactly the valid suffixes of one summarized prefix, and each transition preserves tightness, numeric residue, digit-sum residue, and automaton progress. For $D$ digits, moduli $m,u$, and $A$ automaton states, time is $O(10DmuA)$ and space is $O(DmuA)$ up to constant flags.

Implementation, Complexity and Engineering

The implementation combines value and digit-sum congruences with one forbidden substring. A KMP automaton avoids storing suffix strings. Negative upper bounds count nothing; range subtraction and zero semantics are explicit; invalid moduli and patterns are rejected.

from functools import lru_cache


def automaton(pattern):
    if pattern is None:
        return [[0] * 10], 1
    if not isinstance(pattern, str) or not pattern or not pattern.isdigit():
        raise ValueError("pattern must be nonempty digits")
    prefix = [0] * len(pattern)
    border = 0
    for i in range(1, len(pattern)):
        while border and pattern[i] != pattern[border]:
            border = prefix[border - 1]
        if pattern[i] == pattern[border]:
            border += 1
        prefix[i] = border
    transitions = [[0] * 10 for _ in pattern]
    for state in range(len(pattern)):
        for digit in range(10):
            char = str(digit)
            next_state = state
            while next_state and pattern[next_state] != char:
                next_state = prefix[next_state - 1]
            if pattern[next_state] == char:
                next_state += 1
            transitions[state][digit] = next_state
    return transitions, len(pattern)


def count_up_to(bound, value_modulus, value_target=0,
                sum_modulus=1, sum_target=0,
                forbidden=None, include_zero=False):
    if not isinstance(bound, int) or isinstance(bound, bool):
        raise TypeError("bound must be integer")
    if value_modulus <= 0 or sum_modulus <= 0:
        raise ValueError("moduli must be positive")
    if bound < 0:
        return 0
    digits = tuple(map(int, str(bound)))
    value_target %= value_modulus
    sum_target %= sum_modulus
    transitions, accepting = automaton(forbidden)

    @lru_cache(None)
    def solve(position, tight, started, remainder, digit_sum, state):
        if position == len(digits):
            if not started:
                return int(include_zero and value_target == 0 and sum_target == 0)
            return int(remainder == value_target and digit_sum == sum_target)
        upper = digits[position] if tight else 9
        total = 0
        for digit in range(upper + 1):
            next_tight = tight and digit == upper
            if not started and digit == 0:
                total += solve(position + 1, next_tight, False, 0, 0, 0)
                continue
            next_state = transitions[state][digit] if forbidden else 0
            if forbidden and next_state == accepting:
                continue
            total += solve(position + 1, next_tight, True,
                           (10 * remainder + digit) % value_modulus,
                           (digit_sum + digit) % sum_modulus,
                           next_state)
        return total
    return solve(0, True, False, 0, 0, 0)


def count_range(low, high, **conditions):
    if low > high:
        return 0
    return count_up_to(high, **conditions) - count_up_to(low - 1, **conditions)


def brute(low, high, **conditions):
    total = 0
    for value in range(max(0, low), high + 1):
        if value == 0 and not conditions.get("include_zero", False):
            continue
        text = str(value)
        forbidden = conditions.get("forbidden")
        if forbidden and forbidden in text:
            continue
        if value % conditions["value_modulus"] != conditions.get("value_target", 0) % conditions["value_modulus"]:
            continue
        if sum(map(int, text)) % conditions.get("sum_modulus", 1) != conditions.get("sum_target", 0) % conditions.get("sum_modulus", 1):
            continue
        total += 1
    return total


conditions = dict(value_modulus=7, value_target=2,
                  sum_modulus=3, sum_target=0,
                  forbidden="13", include_zero=False)
for high in (0, 9, 99, 500, 5000):
    assert count_range(0, high, **conditions) == brute(0, high, **conditions)
for low, high in ((1, 100), (37, 999), (1000, 2500)):
    assert count_range(low, high, **conditions) == brute(low, high, **conditions)

zero = dict(value_modulus=5, value_target=0,
            sum_modulus=2, sum_target=0,
            forbidden="00", include_zero=True)
assert count_range(0, 0, **zero) == 1
assert count_range(1, 0, **conditions) == 0

for operation in (lambda: count_up_to(100, 0),
                  lambda: count_up_to(100, 7, forbidden="1x")):
    try:
        operation()
    except ValueError:
        pass
    else:
        raise AssertionError("invalid input accepted")

print("all tests passed")

Choice	Benefit	Failure mode	Mitigation
Tight recursion	Handles arbitrary bounds	Wrong update miscounts	Compare with current bound digit
`started` flag	Separates padding	Padding may trigger patterns	Delay updates until start
Remainder state	Only $O(m)$ values	Large modulus expands state	Estimate product state first
KMP automaton	Compact pattern progress	Many patterns need larger automaton	Use Aho–Corasick and prune
Prefix subtraction	Reuses one solver	Manual decrement errors	Compute $L-1$ as an integer
Memoization	Collapses equivalent prefixes	Deep recursion may hit limits	Use iterative layers when needed

Applications, Case Studies and Exercises

Count $x\le500$ with residue $2$ modulo $7$, digit sum divisible by $3$, and no substring 13; distinct prefixes merge whenever their state tuples agree. In larger identifier policies, estimate the product of all modular and automaton dimensions before implementation, then minimize and prune unreachable states.

Practice

Apply Digit DP with Modular Constraints

Case study 1. Trace prefixes for the bound $500$ under residue, sum, and forbidden-13 constraints. Success means the result matches brute force and the 13 transition is rejected.

Case study 2. Count twelve-digit identifiers with remainder modulo $97$, digit sum modulo $9$, and several forbidden patterns. Validate a six-digit reduction by enumeration. Success requires matching range subtraction and explicit zero semantics.

Exercises. Prove the residue transition; add exact digit frequencies; expose a padding-zero pattern bug; replace KMP with Aho–Corasick; measure reachable versus theoretical product states.

Use enumeration for tiny ranges, digit DP for compact arithmetic state, and a minimized product automaton for pattern constraints. Never leave zero semantics implicit, feed padding zeros into the representation accidentally, or multiply state dimensions without estimating reachability.

Cookie Consent