Digit dynamic programming (digit DP) is a technique used to count numbers within a range ([l, r]) that satisfy specific digit-based constraints. The standard approach involves transforming the problem into computing (F(r) - F(l-1)), where (F(x)) counts valid numbers from 0 to (x).

The solution typically uses memoized recursion over the digits of the number, tracking constraints such as tight bounds (whether the prefix matches the upper limit) and leading zeros.

Example 1: Windy Numbers

A Windy number has adjacent digits differing by atleast 2. To count such numbers in ([l, r]), compute (F(r) - F(l-1)).

The recursive function processes each digit position, ensuring the absolute difference condition holds unless leading zeros are still being skipped.

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

template <typename T>
void read(T& t) {
    t = 0; char ch = getchar(); int sign = 1;
    while (ch < '0' || ch > '9') { if (ch == '-') sign = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { t = t * 10 + (ch - '0'); ch = getchar(); }
    t *= sign;
}

const int MAX_DIGITS = 20;
int dp[MAX_DIGITS][10];
int digits[MAX_DIGITS], len;

int solve(int pos, int last, bool tight, bool started) {
    if (pos == len) return started ? 1 : 0;
    if (!tight && started && dp[pos][last] != -1) return dp[pos][last];
    
    int limit = tight ? digits[pos] : 9;
    int total = 0;
    for (int d = 0; d <= limit; ++d) {
        bool new_started = started || (d != 0);
        bool valid = !new_started || abs(d - last) >= 2;
        if (valid) {
            total += solve(pos + 1, d, tight && (d == limit), new_started);
        }
    }
    
    if (!tight && started) dp[pos][last] = total;
    return total;
}

int countWindy(int n) {
    if (n < 0) return 0;
    len = 0;
    if (n == 0) digits[len++] = 0;
    else {
        while (n) {
            digits[len++] = n % 10;
            n /= 10;
        }
        reverse(digits, digits + len);
    }
    memset(dp, -1, sizeof(dp));
    return solve(0, 0, true, false);
}

int main() {
    int L, R;
    read(L); read(R);
    cout << countWindy(R) - countWindy(L - 1) << endl;
    return 0;
}

Example 2: Product of Counts of Set Bits

Given (n), compute the product over all integers from 1 to (n) of the count of 1s in their binary representation, modulo (10^7 + 7).

Since the number of set bits is small (at most ~60 for 64-bit numbers), iterate over possible bit counts (k). For each (k), count how many numbers in ([1, n]) have exactly (k) ones using digit DP on binary digits. Multiply (k^{\text{count}}) into the result.

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

typedef long long ll;
const ll MOD = 10000007;

ll modPow(ll base, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

ll dp[65][65];
int bin[65], len;

ll dfs(int pos, int ones, bool tight) {
    if (ones > len) return 0;
    if (pos == len) return (ones == 0) ? 1 : 0;
    if (!tight && dp[pos][ones] != -1) return dp[pos][ones];
    
    int limit = tight ? bin[pos] : 1;
    ll total = 0;
    for (int b = 0; b <= limit; ++b) {
        total += dfs(pos + 1, ones - b, tight && (b == limit));
    }
    
    if (!tight) dp[pos][ones] = total;
    return total;
}

ll solve(ll n) {
    if (n <= 0) return 1;
    len = 0;
    while (n) {
        bin[len++] = n & 1;
        n >>= 1;
    }
    reverse(bin, bin + len);
    
    ll result = 1;
    for (int k = 1; k <= len; ++k) {
        memset(dp, -1, sizeof(dp));
        ll cnt = dfs(0, k, true);
        result = (result * modPow(k, cnt)) % MOD;
    }
    return result;
}

int main() {
    ll n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}