Digit DP: как посчитать количество чисел от 1 до N, в записи которых нет цифры 7?
Дано $N$ до $10^{18}$. Нужно число целых от 1 до $N$, в десятичной записи которых не встречается цифра 7. Перебор до $N$ нереален. Знаю термин «цифровое ДП», но не понимаю, как устроено состояние и что такое флаг «tight/прижатость к границе».
2 ответа
Digit DP строит число поразрядно слева направо. Состояние: позиция цифры pos + флаг tight (прижаты ли мы к префиксу самого N) + (опционально) флаг leading_zero и любые накопленные характеристики.
tight = true означает, что все предыдущие цифры совпали с N, поэтому текущую цифру нельзя ставить больше, чем у N. Как только поставили меньшую — tight сбрасывается, и дальше любые цифры свободны.
string s; // десятичная запись N
long long memo[20][2];
bool vis[20][2];
long long go(int pos, bool tight) {
if (pos == (int)s.size()) return 1; // собрали корректное число
if (!tight && vis[pos][0]) return memo[pos][0];
int hi = tight ? (s[pos] - '0') : 9;
long long res = 0;
for (int d = 0; d <= hi; ++d) {
if (d == 7) continue; // запрещаем цифру 7
res += go(pos + 1, tight && (d == hi));
}
if (!tight) { vis[pos][0] = true; memo[pos][0] = res; }
return res;
}
// вызов: count(0..N) = go(0, true); затем вычесть 1 за число 0
Мемоизируем только состояния с tight=false — их $O(\text{позиций})$, и они переиспользуются. Время $O(\text{len} \cdot 10)$ на состояние, всего $O(\text{len}\cdot 10)$ (len $\le 19$). Память $O(\text{len})$.
Два важных нюанса.
1. Почему мемоизация только при tight=false. Когда tight=true, верхняя граница цифры зависит от конкретного префикса N, и такое состояние посещается ровно один раз вдоль «границы» — кешировать его нельзя (для другого N оно другое). А tight=false означает «дальше любые цифры», результат зависит лишь от pos (и других накопленных полей) → кешируется.
2. Ведущие нули и диапазон [L, R]. Если нужно [L, R], считаем f(R) - f(L-1). Если условие чувствительно к длине (например, «нет цифры 7» — нечувствительно, а «ровно k цифр» — чувствительно), добавляй флаг leading_zero в состояние. Здесь, к слову, для «нет 7» есть и прямая формула, но digit DP обобщается на любые условия (сумма цифр кратна $m$, нет двух одинаковых подряд и т.п.).