Нахождение биномиального коэффициента для больших n и k по модулю m

Во-первых, вам не нужно предварительно вычислять и хранить все возможные значения aCb! они могут быть рассчитаны для каждого случая.

Во-вторых, для особого случая, когда (к < м) и (н < m ^ 2), теорема Лукаса легко сводится к следующему результату:

(n выбрать k) mod m = ((n mod m) выбрать k) mod m

тогда, так как (n mod m) < 10 ^ 9 + 7 вы можете просто использовать код, предложенный @kfx.

Биноминальный коэффициент (n, k) рассчитывается по формуле:

(n, k) = n! / k! / (n - k)!

Чтобы сделать эту работу для большого количества n а также k по модулю m обратите внимание, что:

1. Факториал числа по модулю m можно рассчитать пошагово, в
   каждый шаг приносит результат % m, Однако это будет слишком медленно при n до 10 ^ 18. Так что есть более быстрые методы где сложность ограничена по модулю, и вы можете использовать некоторые из них.

2. Отдел (a / b) mod m равно (a * b^-1) mod m, где b^-1 обратная b по модулю m (то есть, (b * b^-1 = 1) mod m).

Это означает, что:

(n, k) mod m = (n! * (k!)^-1 * ((n - k)!)^-1) mod m

Обратное число может быть эффективно найдено с помощью Расширенный евклидов алгоритм. Предполагая, что у вас разобраны факториалы, остальная часть алгоритма проста, просто следите за целочисленными переполнениями при умножении. Вот ссылочный код, который работает до n=10^9, Для обработки больших чисел факторные вычисления должны быть заменены более эффективным алгоритмом, а код должен быть немного адаптирован, чтобы избежать целочисленных переполнений, но основная идея останется прежней:

#define MOD 1000000007

// Extended Euclidean algorithm
int xGCD(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}

int x1, y1, gcd = xGCD(b, a % b, x1, y1);
x = y1;
y = x1 - (long long)(a / b) * y1;
return gcd;
}

// factorial of n modulo MOD
int modfact(int n) {
int result = 1;
while (n > 1) {
result = (long long)result * n % MOD;
n -= 1;
}
return result;
}

// multiply a and b modulo MOD
int modmult(int a, int b) {
return (long long)a * b % MOD;
}

// inverse of a modulo MOD
int inverse(int a) {
int x, y;
xGCD(a, MOD, x, y);
return x;
}

// binomial coefficient nCk modulo MOD
int bc(int n, int k)
{
return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k)));
}

Мы хотим вычислить nCk (mod p). Я справлюсь, когда 0 <= к <= p-2, потому что теорема Лукаса обрабатывает остальное.

Теорема Вильсона утверждает, что для простого p, (p-1)! = -1 (мод р) или эквивалентно (р-2)! = 1 (мод р) (делением).

Делением: (k!) ^ (- 1) = (p-2)! / (K!) = (P-2) (p-3) … (k + 1) (mod p)

Таким образом, биномиальный коэффициент равен n! / (K! (Nk)!) = N (n-1) … (n-k + 1) / (k!) = N (n-1) … ( n-k + 1) (p-2) (p-3) … (k + 1) (mod p)

Вуаля. Вам не нужно делать какие-либо обратные вычисления или что-то в этом роде. Это также довольно легко кодировать. Пара оптимизаций для рассмотрения: (1) вы можете заменить (p-2) (p-3) … на (-2) (- 3) …; (2) nCk является симметричным в том смысле, что nCk = nC (n-k), поэтому выберите половину, которая требует от вас меньше вычислений.