Как построить треугольник Паскаля динамикой за O(n^2) без модуля и с модулем?
Знаю формулу C(n,k) через факториалы, но в задаче n маленькое (до 1000), а вычислять обратные не хочется. Слышал, что можно просто "треугольником Паскаля". Как заполнить таблицу C[n][k] динамикой и какая будет асимптотика? И как не переполниться, если без модуля?
2 ответа
Основа — рекуррента Паскаля: C(n,k) = C(n-1,k-1) + C(n-1,k), с краями C(n,0) = C(n,n) = 1. Это прямое ДП по таблице:
const int MAXN = 1001;
const int MOD = 1e9 + 7;
long long C[MAXN][MAXN];
void pascal() {
for (int n = 0; n < MAXN; n++) {
C[n][0] = 1;
for (int k = 1; k <= n; k++)
C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MOD;
}
}
Асимптотика — O(n^2) по времени и O(n^2) по памяти. Плюс метода: не нужны ни простой модуль, ни обратные элементы — складываем по любому модулю. Минус: квадратная память, поэтому при n > ~5000 уже неудобно (для 1000 это всего ~1М long long, нормально).
Без модуля C(n,k) растёт экспоненциально: C(60,30) уже не влезает в long long (~1.18e17 — влезает, но C(67,33) переполнит). Так что без модуля таблица годится только для маленьких n или unsigned/__int128.
Если нужна только одна строка (фиксированное n), память можно срезать до O(n), считая строку справа налево по той же рекуррентте, либо «множительной» формулой C(n,k) = C(n,k-1) * (n-k+1) / k — последнее даёт строку за O(n) без таблицы, но требует точного деления (тут оно всегда целое) или модульного обратного.