Тема: Большой Биномиальный коэффициент
Привет
Что у нас есть из алгоритмов что б найти (C[n, k]) для K <= N < 10^9
по _не простому_ модулю M < 10 ^ 5
?
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » Большой Биномиальный коэффициент
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Привет
Что у нас есть из алгоритмов что б найти (C[n, k]) для K <= N < 10^9
по _не простому_ модулю M < 10 ^ 5
?
Может быть, получится развить это?
Так же побьём всё на блоки длины P, а в каждом все числа сократим на gcd с P, от хвоста запустимся рекурсивно.
Но, как минимум, плохо то, что асимптотика серьёзно зависит P.
В этой ветке обсуждается взятие числа Каталана (а это тоже биномиальный коэффициент) по модулю-
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) проходит.
"если n>=m бин коэф делится на M" Не похоже что правда. С[1000000000][999999999] = 1000000000
Для составного модуля вряд ли есть что-нибудь умнее, чем разложить его на простые и потом по китайской теореме восстановить.
Так тоже не получится. разложить на простые и восстановить получится только если M "square-free".
Так тоже не получится. разложить на простые и восстановить получится только если M "square-free".
А точно ли? Китайская теорема работает, даже когда модули не простые, главное - их взаимная простота.
Посчитаем ответ по каждому модулю pi_^qi, и запустим Гарнера.
То что Китайская теорема работает это ясно - я имел ввиду что подсчитать коэффициент по модулю pi^qi не сильно нам упростит жизнь если хоть у одного qi >1.
как мы например будем считать коэффициент по модулю 16...
По моему посчитать по модулю 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.
Спасибо, Ярослав. Буду пробовать.
Не получилось.
В формуле ошибка при группировке (1*2*.. * (p-1)) и ((p + 1)*(p + 2)...
так как мы вычисляем по модулю (p ^ q) -> p + 1 != 1)
например p = 3, q = 2 у нас не получится сгруппировать (1 * 2) и (4 * 5)
Пробую группами не по p а по p^q тоже фигня получается.
Так в первой скобке же не 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
Все получилось. Спасибо большое
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » Большой Биномиальный коэффициент