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

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

Найдите функцию Эйлера биномиального коэффициента 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)!), и я не знаю, как его найти.

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

Любая помощь будет оценена по достоинству.


c++ algorithm binomial-coefficients
person Legolas131    schedule 28.05.2020    source источник
comment
T(n,m) = T(n-1,m-1)+T(n-1,m) - это рекурсивное соотношение для нахождения биномиальных коэффициентов. Теперь я думаю, что вы можете двигаться дальше.   -  person aravind    schedule 28.05.2020
comment
@aravind да, но как выразить фи (х + у) через фи (х), фи (у)?   -  person Legolas131    schedule 28.05.2020

Ответы (1)


arrow_upward
2
arrow_downward

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

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

Теперь у вас есть 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, но, похоже, вы уже знаете, как работает деление в кольце по модулю.

person Paul Hankin    schedule 28.05.2020