1

Тема: Большой Биномиальный коэффициент

Привет

Что у нас есть из алгоритмов что б найти  (C[n, k])  для K <= N < 10^9
по _не простому_ модулю M < 10 ^ 5

?

2

Re: Большой Биномиальный коэффициент

Может быть, получится развить это?

Так же побьём всё на блоки длины P, а в каждом все числа сократим на gcd с P, от хвоста запустимся рекурсивно.

Но, как минимум, плохо то, что асимптотика серьёзно зависит P.

3

Re: Большой Биномиальный коэффициент

В этой ветке обсуждается взятие числа Каталана (а это тоже биномиальный коэффициент) по модулю-
http://e-maxx.ru/forum/viewtopic.php?id=172 (первый пост в той ветке- идея, последний пост - рассмотрение одного хитрого случая, у тебя то же самое должно пройти)
Единственное отличие: там n,k <=100000 и решение за O(N) проходит, а у тебя это не пройдет - но зато у тебя модуль M=100000 и ты можешь отсечь случай, где n,k>=100000 одним ифом - если n>=m бин коэф делится на M и ответ 0, иначе М<100000 и O(N) проходит.

4

Re: Большой Биномиальный коэффициент

"если n>=m бин коэф делится на M"    Не похоже что правда. С[1000000000][999999999] = 1000000000

5

Re: Большой Биномиальный коэффициент

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

6

Re: Большой Биномиальный коэффициент

Так тоже не получится.  разложить на простые и восстановить получится только если M "square-free".

7

Re: Большой Биномиальный коэффициент

Oleg пишет:

Так тоже не получится.  разложить на простые и восстановить получится только если M "square-free".

А точно ли? Китайская теорема работает, даже когда модули не простые, главное - их взаимная простота.

Посчитаем ответ по каждому модулю pi_^qi, и запустим Гарнера.

8

Re: Большой Биномиальный коэффициент

То что Китайская теорема работает это ясно - я имел ввиду что подсчитать коэффициент по модулю pi^qi не сильно нам упростит жизнь если хоть у одного qi >1.

как мы например будем считать коэффициент по модулю 16...

9

Re: Большой Биномиальный коэффициент

По моему посчитать по модулю p^q не проблема. В начале найдем степень вхождения p в числитель и знаменатель и сразу домножим ответ на pi в нужной степени. Затем посчитаем N!/p^max, K!/p^max и (N-K)!/p^max (все это по модулю p^q). Можем записать (без ограничения общности считаем что N не кратно p):
N!/p^max = [1*2*...*(p-1)*(p/p^max)]*[(p+1)*(p+2)*...*(2p-1)*(2p/p^max)]*...*[...*N]

Перепишем это как
N!/p^max = 1*2*...*(p-1)*(p+1)*...*(2p-1)*(2p+1)*...*N*[(p/p^max)*(2p/p^max)*...*(floor(N/p)*p/p^max)]

Из того что x*p/p^max = x/p^max следует:
(p/p^max)*(2p/p^max)*...*(floor(N/p)*p/p^max) = (1/p^max)*(2/p^max)*...*(floor(N/p)/p^max) = floor(N/p)!/p^max

Получаем, что:
N!/p^max = [1*2*...*(p-1)*(p+1)*...*(p^q-1)]^floor(N/(p^q)) * [1*2*...*(p-1)*(p+1)*...*(N mod p^q)] * floor(N/p)!/p^max (mod p^q)

Последний множитель посчитаем рекурсивно. Первые 2 квадратных скобки можно найти за O(p^q) и возведение в степень сделать за log(N). Следовательно, мы можем за O(p^q * logN) посчитать N!/p^max по модулю p^q.

K!/p^max и (N-K)!/p^max взаимнопросты с p^q, следовательно, мы можем найти обратные к ним и поделить по модулю чтобы найти C(N,K) mod p^q.

10

Re: Большой Биномиальный коэффициент

Спасибо, Ярослав. Буду пробовать.

11

Re: Большой Биномиальный коэффициент

Не получилось.
В формуле ошибка при группировке (1*2*.. * (p-1))   и ((p + 1)*(p + 2)... 
так как мы вычисляем по модулю (p ^ q)  -> p + 1 != 1)


например p = 3, q = 2   у нас не получится сгруппировать (1 * 2) и (4 * 5)


Пробую группами не по p а по p^q тоже фигня  получается.

12 Отредактировано KADR (2010-12-22 09:25:38)

Re: Большой Биномиальный коэффициент

Так в первой скобке же не p-1, а p^q-p^(q-1) слагаемых.
При p = 3, q = 2 и N=22 имеем:

N!/p^max=(1*2)*(4*5)*(7*8)*(10*11)*(13*14)*(16*17)*(19*20)*(22)*(3*6*9*12*15*18*21)/p^max=(1*2*4*5*7*8)^2 * (19*20*22) * 7!/p^max

13

Re: Большой Биномиальный коэффициент

Все получилось. Спасибо большое smile