Счётное ДП по модулю: как считать число способов и где обычно теряют корректность с остатком?
Во многих задачах просят «число способов по модулю $10^9+7$». Я просто беру остаток в конце — и получаю WA, потому что промежуточные суммы переполняют long long. Как правильно вести счётное ДП по модулю и какие операции опасны?
2 ответа
Главное правило: брать остаток на каждом шаге, а не в конце. Любая сумма или произведение, которое может перерасти тип, сразу приводи по модулю.
const long long MOD = 1e9 + 7;
// сложение
dp[i] = (dp[i] + dp[j]) % MOD;
// умножение — приводи к long long ПЕРЕД умножением
dp[i] = (dp[i] * ways) % MOD; // оба long long -> произведение < ~10^18, влезает
Почему это безопасно: остатки < MOD ≈ 10^9. Произведение двух таких $< 10^{18}$ — влезает в long long ($\approx 9.2\cdot10^{18}$). Сумма двух — тем более.
Опасные места:
- Вычитание даёт отрицательное число: пиши
(a - b % MOD + MOD) % MOD. - Деление по модулю — это умножение на обратный по Ферма:
inv(b) = b^(MOD-2) mod MOD(бинарное возведение в степень), MOD простое. - Произведение трёх и более множителей — приводи после каждого умножения, не копи.
Корректность счёта от модуля не страдает: мы считаем то же число способов, просто в кольце вычетов. Сложность не меняется — это та же таблица ДП, плюс константа на % MOD.
Частая засада — переполнение при умножении int * int. Даже если оба операнда < 10^9 (влезают в int), их произведение $\sim 10^{18}$ в int переполнится ещё до взятия модуля. Лечение: храни ДП в long long, либо явно кастуй (long long)a * b % MOD.
Ещё: если в задаче вычитание (например, включение-исключение в счётном ДП), никогда не делай % MOD от потенциально отрицательного без + MOD. И не бери модуль от сравнений — dp[i] % MOD == 0 и dp[i] == 0 это разные вещи, для проверки «ноль способов» сравнивай само значение остатка с 0.