Где применяется
1. Задача
Некоторые ответы огромны. Число способов расставить 100 предметов по порядку записывается 158 цифрами. В числе 21000 больше 300 цифр. Обычное целое такие числа не вмещает.
Полное число при этом обычно никому не нужно. Задача говорит: «верни ответ по модулю 1e9+7», то есть дай остаток от деления на это простое число. Скользящий хеш подстроки устроен так же: это большое число, от которого хранят только остаток. Нужен остаток, а огромное число, из которого он получается, хранить не надо.
Ловушка: сначала посчитать всё целиком и взять остаток в конце. В JavaScript целые больше 253 - 1 хранятся неточно, и ошибки об этом нет. К моменту финального % m значение уже испорчено.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сократить дробь до несократимого вида
- перечислить все простые числа до n
- ответ по модулю 1e9+7
- когда снова совпадут два повторяющихся интервала (НОК)
Похоже, но не то
- Битовые манипуляции (Bit manipulation)
Оба работают с самим числом. Та страница про отдельные биты.
- Хеш-множество / словарь (Hash set / map)
Множество простых чисел всё равно надо как-то построить. Решето и есть способ его построить.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Формула отвечает сразу там, где динамика заполняет таблицу. Сначала поищите замкнутую форму.
- Префиксные суммы (Prefix sums)
Префиксные суммы отвечают по сохранённым значениям. Здесь ответ следует из свойств самих чисел.
НОД стоит O(log от меньшего значения). Решето до 1e7 нормально, а до 1e9 уже нет.
На LeetCode
Задачи на подсчёт с припиской «верни ответ по модулю 10^9 + 7». Бери остаток после каждого сложения и умножения, а умножение делай в BigInt, ведь два остатка около 10^9 дают произведение больше 2^53.
На чётных позициях 5 вариантов, на нечётных 4, так что ответ это 5^a на 4^b при n до 10^15, два вызова powMod из урока.
Сталкиваются все варианты, кроме двух, когда все идут по часовой или все против, так что ответ это 2^n минус 2, и прибавь модуль перед остатком, чтобы результат не ушёл в минус.
Для каждого i умножай результат на 2 в степени длины i в битах, прибавляй i и бери остаток. Результат меньше 2^30, так что произведение меньше 2^47.
Лучшее произведение это 2^p минус 1, умноженное на 2^p минус 2 в степени 2^(p-1) минус 1. Для больших p эта степень больше 2^53, так что держи всё в BigInt.