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