Найти функцию Эйлера биномиального коэффициента

Question

Я пытался решить эту проблему:

Найти тотальную функцию Эйлера биномиальный коэффициент C(n, m) = n! / (m! (n - m)!) по модулю 10 ^ 9 + 7, m <= n < 2 * 10^5.

Одна из моих идей заключалась в том, что, во-первых, мы можем предварительно вычислить значения phi(i) для всех i от 1 до n за линейное время, а также мы можем вычислить все обратные числа к числам от 1 до n по модулю 10 ^ 9 + 7, используя, например, малая теорема Ферма. После этого мы знаем, что, в общем, phi(m * n) = phi(m) * phi(n) * (d / fi(d)), d = gcd(m, n). Поскольку мы знаем, что gcd((x - 1)!, x) = 1, if x is prime, 2 if x = 4, and x in all other cases, мы можем вычислить phi(x!) по модулю 10 ^ 9 + 7 за линейное время. Однако на последнем этапе нам нужно вычислить phi(n! / ((m! (n - m)!), (если мы уже знаем функцию для факториалов), поэтому, если мы используем этот метод, мы должны знать gcd(C(n, m), m! (n - m)!), и я не знаю, как чтобы найти его.

Я тоже думал о факторизации биномиального коэффициента, но, похоже, нет эффективного способа сделать это.

Любая помощь будет принята с благодарностью.

Answer 1

Сначала разложите на множители все числа 1 .. (2 * 10 ^ 5) как произведения степеней простых чисел.

Теперь разложите на множители n! / K! = n (n-1) (n-2) ... (n-k + 1) как произведение степеней простых чисел путем умножения множителей отдельных частей. Факторизуйте (nk)! как продукт основных сил. Вычтите последние степени из первых (чтобы учесть деление).

Теперь у вас есть C (n, k) как произведение степеней простых чисел. Используйте формулу phi (N) = N * prod (1 - 1 / p для p | N), чтобы вычислить phi (C (n, k)), что очень просто, учитывая, что вы вычислили список всех простые степени, которые делят C (n, k) на втором этапе.

Например:

phi(C(9, 4)) = 9*8*7*6*5 / 5*4*3*2*1
9*8*7*6*5 = 3*3 * 2*2*2 * 7 * 3*2 * 5 = 7*5*3^3*2^4
5*4*3*2*1 = 5 * 2*2 * 3 * 2 * 1 = 5*3*2^3

9*8*7*6*5/(5*4*3*2*1) = 7*3^2*2

phi(C(9, 4)) = 7*3^2*2 * (1 - 1/7) * (1 - 1/3) * (1 - 1/2) = 36

Я сделал это целыми числами, а не целыми числами по модулю M, но похоже, вы уже знаете, как работает деление в кольце по модулю.