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

Question

Я хочу, чтобы вычислить NCK тойт со следующими ограничениями:

п < = 10^18

к < = 10^5

м = 10^9 + 7

Я прочитал эту статью:

Calculating Binomial Coefficient (nCk) for large n & k

Но здесь значение т является 1009. Следовательно, используя теорему Лукаса, нам нужно только вычислить 1009 * 1009 различных значений ACB, где а, Ь < = 1009

Как сделать это с выше ограничений. Я не могу создать массив сложности O (m * k) с заданными ограничениями.

Помощь!

Answer 1

Просто используйте тот факт, что

(n, k) = n!/k!/(n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1] 

так что вы на самом деле есть только 2*k=2*10^5 факторы. Для обратного номера вы можете использовать предложение kfx, так как ваш m является простым.

Answer 2

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

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

Для того, чтобы сделать эту работу для большого числа n и k по модулю m заметить, что:

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

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

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

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

Обратный ряд можно эффективно найти с помощью Extended Euclidean algorithm. Предполагая, что вы определили факториал, остальная часть алгоритма проста, просто следите за целыми переполнениями при умножении. Вот код ссылки, который работает до 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))); 
} 

Answer 3

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

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

(п выбрать к) по модулю т = ((п mod m) выберите k) mod m

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