MITM: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Содержимое страницы заменено на «* MITM в задачах на числа»)
Метка: замена
Строка 1: Строка 1:
==Ограничения==
+
* [[MITM в задачах на числа]]
 
 
Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^{14}$, решим задачу количество чисел < $k$ с суммой цифр - $s$
 
 
 
==Альтернативное решение без ДП по цифрам==
 
 
 
Давайте разделим число на левую часть(большие 7 разрядов) и правую(меньшие 7 разрядов). Давайте для всех чисел правой части предподсчитаем, сколько из них имеют сумму $x$ и запишем это в массив подсчет, затем будем перебирать левую часть, пусть и числа из левой части сумма - $x$, тогда нам нужно найти количество правых частей с суммой $S - x$(это просто обращение к массиву подсчета), тогда мы научились решать задачу за $\sqrt(k)$
 
 
 
{{Автор|Глеб Лобанов|glebodin}}
 

Версия 20:30, 25 марта 2020