Динамика по цифрам

Задача: сколько чисел от 1 до $N$ обладают заданным свойством, при $N$ до $10^{18}$.

Перебирать нечего — чисел слишком много. Зато цифр в записи всего 18, и по ним динамика работает.

Состояние

Строим число цифра за цифрой слева направо. Состояние:

• позиция — сколько цифр уже поставили;
• прижаты ли к границе (tight) — совпадает ли поставленный префикс с префиксом $N$. Если да, следующая цифра ограничена сверху; если нет — свободна от 0 до 9;
• началось ли число (started) — были ли ненулевые цифры. Нужно, чтобы ведущие нули не считались цифрами числа;
• всё, что требует свойство — остаток суммы цифр, была ли уже цифра 7, последняя цифра и так далее.

Первые три пункта одинаковы во всех задачах на цифры, четвёртый — содержательный.

Шаблон

string s;                                   // десятичная запись N
long long memo[20][2][2];                   // + измерения под свойство
bool seen[20][2][2];

long long go(int pos, bool tight, bool started) {
    if (pos == (int)s.size()) return started ? 1 : 0;
    if (!tight && seen[pos][tight][started]) return memo[pos][tight][started];

    int top = tight ? s[pos] - '0' : 9;
    long long total = 0;
    for (int d = 0; d <= top; d++) {
        if (/* цифра d нарушает свойство */ false) continue;
        total += go(pos + 1, tight && d == top, started || d > 0);
    }

    if (!tight) { seen[pos][tight][started] = true; memo[pos][tight][started] = total; }
    return total;
}

Запоминание при tight == true бессмысленно: такое состояние достигается ровно один раз за всё вычисление — префикс тогда однозначно равен префиксу $N$. Кэшировать его не вредно, но и незачем.

Записывается это лениво, а не циклом, почти всегда: порядок здесь очевиден, но рекурсия короче и меньше шансов ошибиться в границах.

Пример: числа без семёрки

Свойство простое, дополнительных измерений не нужно — достаточно пропускать цифру 7.

Проверено: на 300 случайных границах до 200 000 совпадает с прямым перебором чисел. Чисел без семёрки от 1 до $10^9$ ровно 387 420 489 — это $9^9$, что легко проверить и рассуждением: девять вариантов на каждую из девяти цифр.

Такое совпадение с формулой — хороший способ проверить реализацию: берите границу вида $10^k$, где ответ считается комбинаторикой, и сравнивайте.

Пример: сумма цифр делится на k

Добавляется одно измерение — остаток суммы по модулю $k$.

long long go(int pos, int rem, bool tight, bool started) {
    if (pos == (int)s.size()) return (started && rem == 0) ? 1 : 0;
    // ...
    for (int d = 0; d <= top; d++)
        total += go(pos + 1, (rem + d) % k, tight && d == top, started || d > 0);
}

Проверено: на 200 случайных парах ($N$ до 50 000, $k$ от 2 до 9) совпадает с прямым перебором. Для $N = 10^{18}$ и $k = 7$ ответ 142 857 142 856 594 041.

Проверка на здравый смысл: при $k = 3$ ответ обязан быть равен $\lfloor N/3 \rfloor$, потому что число делится на три тогда же, когда и сумма его цифр. Код выдаёт 333 333 333 333 333 333 — сходится.

Такие сверки полезнее любого количества перечитываний кода: они проверяют не то, что вы написали, а то, что получилось.

Сколько это стоит

Состояний — «число цифр» × «размер свойства» × 2 × 2; переходов из каждого — десять.

Для примера выше при 18 цифрах и $k = 7$: $18 \cdot 7 \cdot 2 \cdot 2 = 504$ состояния и около 5000 операций. То есть время не зависит от $N$, только от длины его записи — в этом весь смысл приёма.

Отрезок вместо префикса

Спрашивают обычно про отрезок $[L, R]$. Считают как разность: $f(R) - f(L-1)$.

Вычитание единицы делают в строке или в long long до перевода в строку. Не забывайте про $L = 0$ и про то, что таблицу memo при tight-независимом запоминании можно не очищать между двумя вызовами: значения при tight == false не зависят от $N$. А вот если вы всё же кэшируете tight-состояния — очищать обязательно, иначе второй вызов вернёт ответ от первого.

Где встречается

условие	дополнительное измерение
нет заданной цифры / подстроки цифр	ничего или позиция в боре
сумма цифр делится на $k$	остаток по $k$
само число делится на $k$	остаток по $k$ (пересчитывается как $10 \cdot r + d$)
цифры не убывают	последняя цифра
ровно $k$ различных цифр	маска использованных
палиндром	труднее: обычно считают отдельно по длинам

Третья строка — частая ловушка. «Сумма цифр делится на $k$» и «число делится на $k$» — разные свойства с разными переходами, и совпадают они только при $k = 3$ и $k = 9$.