Когда комбинаторный ответ нужно брать по модулю, а когда влезает в long long?
Часто вижу в условиях «выведите ответ по модулю 1e9+7», а иногда просят точное число. Как заранее понять, что ответ переполнит 64-битный тип и нужен модуль? Есть ли быстрая прикидка, до каких n факториалы и C(n,k) ещё влезают в long long?
2 ответа
Ориентиры для знаковых 64 бит (макс ≈ 9.22·10^18):
- Факториал: 20! ≈ 2.4·10^18 влезает, 21! ≈ 5.1·10^19 — уже переполнение. То есть n! помещается только до n=20.
- Степень: 2^62 ≈ 4.6·10^18 влезает, 2^63 переполняет знаковый тип. k^n быстро вылетает.
- C(2n,n) (центральный коэффициент, самый большой в строке): растёт ≈ 4^n/√(πn). C(62,31) ≈ 4.7·10^17 влезает, C(68,34) ≈ 2.8·10^19 — переполнение. Грубо: C(n, n/2) безопасен примерно до n ≈ 66.
Правило: если в условии n больше нескольких десятков и ответ — это факториал, степень или сочетание, он почти наверняка астрономический → ждут ответ по модулю (1e9+7 или 998244353). Если просят ТОЧНОЕ значение при больших n — нужна длинная арифметика (Python, __int128 не хватит, или bignum).
// признак: если в условии есть "mod 1000000007" — считай всё в long long с % после каждого умножения
const long long MOD = 1000000007;
long long mul(long long a, long long b){ return a % MOD * (b % MOD) % MOD; }
Сложность тут ни при чём — речь о РАЗМЕРЕ числа. Сам признак «нужен ли модуль» читается прямо из ограничений на n и формулировки вывода.
Полезная проверка на переполнение БЕЗ модуля (когда ответ обязан влезть, но хочешь подстраховаться): при умножении a*b проверяй if (a != 0 && res / a != b) overflow; или считай в __int128 и сравнивай с границей. А при множительном вычислении C(n,k) удерживай значение маленьким через симметрию k = min(k, n−k) — это отодвигает переполнение промежутка.