Digit DP
Digit DP
What is Digit DP?
Digit DP is used for problems like:
- count numbers in a range
- with some property based on digits
- where can be very large (often up to or even bigger as a string)
The standard trick is:
Digit DP
Digit DP is used for problems like:
The standard trick is:
where = number of valid integers in .
Let the decimal digits of be stored in a string s.
Define a DP state like:
Where:
pos = current digit indextight = whether prefix is equal to bound prefix (1) or already smaller (0)started = whether we already placed a non-leading-zero digitstate = problem-specific info (sum, remainder, count, last digit, mask, ...)Transition:
d from 0 to limitlimit = s[pos] if tight=1, else 9Problem: Count numbers in with digit sum divisible by
Let:
= number of ways to build prefix up to pos, where rem is digit sum modulo .
We store only remainder (not full sum), which is much better.
If we place digit d, then:
(Usually if started = 0 and d = 0, we still allow it; this is just leading zeros.
At the end, subtract 1 if you want to exclude zero.)
If number length is N, complexity is roughly:
Do not store full digit sum if only divisibility matters.
Store:
instead of sum.
tight = 0A common optimization:
tight = 0 are reusabletight = 1 depend on the exact bound prefixSo many solutions memoize only the loose states (tight = 0) and save memory.
Leading zeros are part of Digit DP and must be handled consistently.
Typical choices:
started flag#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;
int D;
ll memo[20][2][2][105];
bool vis[20][2][2][105];
ll dfs(int pos, int tight, int started, int rem) {
if (pos == (int)s.size()) {
// exclude 0 by requiring started == 1
return (started && rem == 0) ? 1 : 0;
}
if (vis[pos][tight][started][rem]) return memo[pos][tight][started][rem];
vis[pos][tight][started][rem] = true;
int lim = tight ? (s[pos] - '0') : 9;
ll ans = 0;
for (int d = 0; d <= lim; d++) {
int ntight = (tight && d == lim);
int nstarted = started || (d != 0);
int nrem = rem;
if (nstarted) nrem = (rem + d) % D;
ans += dfs(pos + 1, ntight, nstarted, nrem);
}
return memo[pos][tight][started][rem] = ans;
}
ll solve(long long x, int modD) {
if (x < 0) return 0;
s = to_string(x);
D = modD;
memset(vis, 0, sizeof(vis));
return dfs(0, 1, 0, 0);
}
int main() {
long long L, R;
cin >> L >> R >> D;
cout << solve(R, D) - solve(L - 1, D) << "\n";
return 0;
}