MITM в задачах на числа

Материал из Algocode wiki
Версия от 20:31, 25 марта 2020; Глеб (обсуждение | вклад) (Новая страница: «==Ограничения== Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, напри...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Ограничения

Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^{14}$, решим задачу количество чисел < $k$ с суммой цифр - $s$

Альтернативное решение без ДП по цифрам

Давайте разделим число на левую часть(большие 7 разрядов) и правую(меньшие 7 разрядов). Давайте для всех чисел правой части предподсчитаем, сколько из них имеют сумму $x$ и запишем это в массив подсчет, затем будем перебирать левую часть, пусть и числа из левой части сумма - $x$, тогда нам нужно найти количество правых частей с суммой $S - x$(это просто обращение к массиву подсчета), тогда мы научились решать задачу за $\sqrt(k)$



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin