2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Быстро вычислить мультиномиальный коэффициент mod P
Сообщение07.04.2014, 22:44 
Для одной задачи по комбинаторике мне нужно вычислить $$\frac {n!}{k_1!k_2!k_3!}$$ где $n = k_1+k_2+k_3$. Вычислять необходимо по простому модулю $P = 10^9 + 7$. В своей программе я перебираю $k_1$ и $k_2$ поэтому вычислять коэффициент необходимо вычислять быстро, т.к. $1\leq k_1,k_2,k_3, n\leq 4000$.
Пока проблема в том, что, зная $f[]$ - массив факториалов по модулю $P$, мы не можем выполнить деление по этому же модулю. Иначе говоря, $$\frac{n!\mod P}{k!\mod P}\neq\frac{n!}{k!}\mod P$$Так как же выполнить вычисления?

 
 
 
 Re: Быстро вычислить мультиномиальный коэффициент mod P
Сообщение08.04.2014, 05:06 
milos в сообщении #846972 писал(а):
Иначе говоря, $$\frac{n!\mod P}{k!\mod P}\neq\frac{n!}{k!}\mod P$$
Это почему же не равно? Если $P$ --- простое число и $n$, $k$ меньше $P$, то равно.

 
 
 
 Re: Быстро вычислить мультиномиальный коэффициент mod P
Сообщение08.04.2014, 09:14 
Если $$n!\geq P$$ то $$\frac{n! \mod P}{k!\mod P}\neq \frac{n!}{k!}\mod P$$ Проверял.

 
 
 
 Re: Быстро вычислить мультиномиальный коэффициент mod P
Сообщение08.04.2014, 09:27 
Если $a\bmod m$ - остаток от деления $a$ на $m$, то равенство
$$\frac{n!\mod P}{k!\mod P}=\frac{n!}{k!}\mod P$$
неверно, но оно нам и не нужно. Вам нужно все целые элементы вложить в $\mathbb{Z}_p$ и считать в нем, а потом полученный ответ поднять до элемента $\mathbb{Z}$. Т.е. пусть $g:x\to g(x)$ - гомоморфизм $\mathbb{Z}\to\mathbb{Z}_p$. Тогда $g\left(\frac{n!}{k!}\right)=\frac{g(n!)}{g(k!)}$ - вот им пользуйтесь, а потом результат из $\mathbb{Z}_p$ возвращайте в $\mathbb{Z}$.
Например:
$p=5,n=3,k=2$
$g\left(\frac{n!}{k!}\right)=g(3)$
$\frac{g(n!)}{g(k!)}=\frac{g(6)}{g(2)}=\frac{g(1)}{g(2)}=g(2^{-1})=g(3)$.

 
 
 
 Re: Быстро вычислить мультиномиальный коэффициент mod P
Сообщение08.04.2014, 11:37 
А как вернуть число из $\mathbb{Z}_p$ в $\mathbb{Z}$?

 
 
 
 Re: Быстро вычислить мультиномиальный коэффициент mod P
Сообщение10.04.2014, 15:24 
Посчитайте знаменатель (назовём его $m$) по модулю $P$ и найдите для него обратный элемент $m^{-1}$ в кольце по данному модулю. Тогда значение вашего коэффициента есть произведение числителя и $m^{-1}$.

Как за $O(\log(n))$ вычислять $m^{-1}$ можете посмотреть здесь http://e-maxx.ru/algo/reverse_element

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group