MITM
Материал из Algocode wiki
Версия от 17:30, 25 марта 2020; Глеб (обсуждение | вклад)
Ограничения
Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^{14}$, решим задачу количество чисел < $k$ с суммой цифр - $s$
Альтернативное решение без ДП по цифрам
Давайте разделим число на левую часть(большие 7 разрядов) и правую(меньшие 7 разрядов). Давайте для всех чисел правой части предподсчитаем, сколько из них имеют сумму $x$ и запишем это в массив подсчет, затем будем перебирать левую часть, пусть и числа из левой части сумма - $x$, тогда нам нужно найти количество правых частей с суммой $S - x$(это просто обращение к массиву подсчета), тогда мы научились решать задачу за $\sqrt(k)$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin