Digit DP
O(digits · states · 10)Count numbers in [0, N] with some digit property by building N digit by digit. The two universal state flags: tight (are we still glued to N's prefix, so the next digit is capped?) and started (have we placed a nonzero digit yet, so leading zeros don't pollute the property?). Answer queries on [a, b] as solve(b) - solve(a-1). The property itself rides along as extra state; here it is the previous digit.
// use it on
CSES: Counting Numbers ↗
Count numbers in [a,b] with no two adjacent equal digits. Exactly this template; a can be 0, so handle solve(-1) = 0 rather than subtracting blindly.
// the code
// count x in [0, n] with no two equal adjacent digits
long long solve(long long n) {
if (n < 0) return 0;
string s = to_string(n);
int L = s.size();
// memo[pos][prev] for the free (not tight, started) states only
vector<vector<long long>> memo(L, vector<long long>(11, -1));
auto rec = [&](auto&& self, int pos, int prev, bool tight, bool started) -> long long {
if (pos == L) return 1;
if (!tight && memo[pos][prev + 1] != -1 && started)
return memo[pos][prev + 1];
long long res = 0;
int hi = tight ? s[pos] - '0' : 9;
for (int d = 0; d <= hi; d++) {
if (started && d == prev) continue;
res += self(self, pos + 1, (started || d) ? d : -1,
tight && d == hi, started || d);
}
if (!tight && started) memo[pos][prev + 1] = res;
return res;
};
return rec(rec, 0, -1, true, false);
}
// answer for [a, b]: solve(b) - solve(a - 1)// more digits & optimization