Цифровая динамика программирования
Digit DP используется для задач вроде:
Стандартный трюк:
где = количество подходящих целых чисел в .
Пусть десятичные цифры хранятся в строке s.
Определим состояние DP так:
Где:
pos = индекс текущей цифрыtight = равен ли префикс префиксу границы (1) или уже меньше (0)started = поставили ли мы уже ненулевую (не ведущий ноль) цифруstate = информация, специфичная для задачи (сумма, остаток, количество, последняя цифра, маска, ...)Переход:
d от 0 до limitlimit = s[pos] если tight=1, иначе 9Задача: Посчитать числа в с суммой цифр, делящейся на
Пусть:
= количество способов построить префикс до pos, где rem — сумма цифр по модулю .
Мы храним только остаток (а не полную сумму), что гораздо лучше.
Если мы ставим цифру d, тогда:
(Обычно если started = 0 и d = 0, мы всё равно разрешаем это; это просто ведущие нули.
В конце вычтите 1, если хотите исключить ноль.)
Если длина числа — N, сложность примерно:
Не храните полную сумму цифр, если важна только делимость.
Храните:
вместо sum.
tight = 0Распространённая оптимизация:
tight = 0 переиспользуемыtight = 1 зависят от точного префикса границыПоэтому многие решения мемоизируют только свободные состояния (tight = 0) и экономят память.
Ведущие нули — часть Digit DP и должны обрабатываться согласованно.
Типичные варианты:
started#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;
}