Быстро вычислить мультиномиальный коэффициент mod P

[milos]

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

$$\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$$

Так как же выполнить вычисления?

[nnosipov]

milos в сообщении #846972 писал(а):

Иначе говоря,

$$\frac{n!\mod P}{k!\mod P}\neq\frac{n!}{k!}\mod P$$

Это почему же не равно? Если $P$ --- простое число и $n$, $k$ меньше $P$, то равно.

[milos]

Если

$$n!\geq P$$

то

$$\frac{n! \mod P}{k!\mod P}\neq \frac{n!}{k!}\mod P$$

Проверял.

[Sonic86]

Если $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)$.

[milos]

А как вернуть число из $\mathbb{Z}_p$ в $\mathbb{Z}$?

[Guliashik]

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

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