Остаток от деления больших биномиальных коэффициентов

[malphunction]

Sonic86 в сообщении #425624 писал(а):

и аналогичное сообщение в первом посте я не понял

Идея такая была: например, считаем $C_{100}^{10}$. Выпишем все числа:

$$ C_{100}^{10} = {{100 \times 99 \times 98 \times 97 \times 96 \times 95 \times 94 \times 93 \times 92 \times 91 } \over {10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2}} $$

Понятно, каждому числу из знаменателя можно сопоставить кратное ему из числителя. Пробегаем знаменатель справа налево, сопоставлям. Например, 2-ке сопоставится 92, 3-ке -- 93 или 96, и т.д. Сопоставление находится за одно деление и несколько сложений, да к тому же числитель умещается в кеше, так что получается очень быстро) Сопоставление не взаимнооднозначно (например, там могут быть простые числа), так что некоторым числам числителя будет соответствовать несколько из знаменателя. Так вот, по сопоставленные числа знаменателя можно сократить, получится что-то типа (пишу по памяти, приблизительно):

$$ C_{100}^{10} = {{10 \times 11 \times 98 \times 97 \times 4 \times 19 \times 94 \times 31 \times 46 \times 13 } \over {{}_1 \times {}_1 \times 8 \times {}_1 \times {}_1 \times {}_1 \times {}_1 \times {}_1 \times {}_1}} $$

Т.е. такой наивный алгоритм в данном примере споткнётся на 8 (соответствующая 96 уже участвовала в сокращении). Но и с этим всё просто: если первый раз не удалось найти кратное число (потому что оно уже задействовано в сокращении), то ищем НОД этих двух чисел, сокращаем, переходим к следующему, это тоже делается быстро, где-то за 5-6 шагов. Например, для этого б.к. восьмерка тоже сокращается. И вот, в результате остается только умножение. Причём числа там прорежены и не вызывают быстрого переполнения разрядной сетки, так что на последующем поиске модуля тоже можно сэкономить.

Так вот, такой вот полуторопроходный алгоритм работает исключительно быстро. $C_{10^5}^{(5 \times 10^4)}$ (самый худший для него случай) считает где-то за 0.005 секунды. Это очень неплохо для моей задачки!

Но!!! Иногда попадаются несократимые таким образом числа. Их где-то 1/50 от чисел знаменателя. Для них приходится делать дополнительную обработку. И вот возня с ними замедляет алгоритм до 3-5 секунд.

Можно оптимальнее подыскивать парные числа, но мне удалось таким образом раза в два лишь ускорить алгоритм, а этого мало :(

[Sonic86]

Ааа! Понял. То есть Вам нужно для всех $k,n$ найти соответствие (желательно взаимно однозначное) $f:A \to B$ множеств $A = \{ 1;2;...;k\}$ и $B = \{ n;n-1;...;n-k+1\}$ так, чтобы $a$ делило $f(a)$. Надо подумать...

[Sonic86]

Я могу предложить такое:
Вы читаете знаменатель с $k$ до $1$. И сокращаете его с числителем за один проход. На примере $C_{50}^{20}$, пусть числитель и знаменатель записаны в 2-х массивах длины $k$ (нумерую элементы массива начиная с 1). У Вас тут $20|40, 19|38, 18|36, ..., 15|30$, причем частное от деления всегда будет равно 2, а номер ячейки массива числителя легко вычислить: номер ячейки $40$ равен $k \[\frac{n}{k} \]$ или даже $n - (n \mod k)$ (чтоб делений не было), а номер каждой следующей ячейки - это номер предыдущей минус 2: $40, 38, 36,$ ... Т.е. за долю прохода можно все эти числа сократить. Далее в знаменателе пойдет число 14, а числа 28 в числителе нету. Тогда начинаем заново: $14 \cdot \[ \frac{50}{14}\] = 42$ и тогда $14|42, 13|39,11|33$ - сокращаем аналогично, частное равно 3 (т.е. не надо его каждый раз считать), только нужно проверять, что еще не было сокращений. И вот так до упора. Скорее всего сократиться не все и что-то придется досокращать с помощью Евклида + я затрудняюсь оценить скорость этого. Но я так считал $C_{2n}^n$ на бумажке всегда, когда не было компа! (я забыл, а теперь вот вспомнил!) + тут после одного прохода в знаменателе остаются всегда небольшие числа, а вероятность того, что на них делится - выше.

[venco]

А чем не понравилось сокращение только простых делителей?
Перебираете все простые числа до $n$ и смотрите сколько раз этот делитель входит в каждый факториал (простая формула). Остатки перемножаете.
И быстро, и не запутаешься.

[malphunction]

Sonic86 в сообщении #425677 писал(а):

malphunction писал(а):

Кто-нибудь, можете объяснить, как применить теорему Вильсона? Особенно для замены деления на умножения??
Хорхе, к сожалению, не отвечает :(

Я могу. Сначала используете формулу Люка и тогда $0 \leq k \leq n <p$, а потом поскольку $(p-1)! \equiv -1 \pmod p$ будет $C_n^k = \frac{n(n-1)...(n-k+1)}{k!} \equiv - \frac{n(n-1)...(n-k+1)(p-1)!}{k!} = $
$= - n(n-1)...(n-k+1) \cdot (k+1)(k+2)...(p-1) \pmod p$

Красота-а! Очень элегантно! :)

-- Ср мар 23, 2011 10:34:32 --

venco в сообщении #425771 писал(а):

А чем не понравилось сокращение только простых делителей?
Перебираете все простые числа до $n$ и смотрите сколько раз этот делитель входит в каждый факториал (простая формула). Остатки перемножаете.
И быстро, и не запутаешься.

Да, вроде сложность получается в районе $10^5$ операций. Попробовал запрограммировать -- действительно, получается быстро, удается вычислять где-то 15000 б.к. ($n < 10^5$) в те самые 3 секунды, это очень хорошо!! Возможно даже, и теорему Люка можно не применять, прям так, с $n < 10^9$ считать, хотя это требует больше памяти.

Теперь вот бьюсь над сокращением. Теорема Люка применяется к простым модулям, поэтому $p$ нужно факторизовать. Простые множители могут входить с не-единичными степенями, и как с этим быть, ещё не придумал. Т.е. если нашли $C^{n_i}_{k_i} \pmod{p_i}$, то как перейти к $C^{n_i}_{k_i} \pmod{{p_i}^{s_i}}$ ? Ну или перейти к $C^n_k \pmod{p}$? Видимо, нужно использовать Китайскую теорему об остатках, ну или посмотреть доказательство теоремы Люка, может, удастся приспособить её и для степеней простых чисел...

[Sonic86]

(venco)

venco писал(а):

А чем не понравилось сокращение только простых делителей?
Перебираете все простые числа до $n$ и смотрите сколько раз этот делитель входит в каждый факториал (простая формула). Остатки перемножаете.
И быстро, и не запутаешься.

Лично мне все нравится, я просто хотел подробно рассмотреть всякие варианты, поскольку задачка явно допускает несколько решений, сравнить которые сложно. Я даже не пишу оценки на всякий случай

А я туплю! Теорема Вильсона - это ведь частный случай более общей теоремы:
Теорема
Пусть $G$ - конечная коммутативная группа. Тогда произведение $\prod\limits_{g \in G}g$ существует и равно$\prod\limits_{g \in G, g^{-1}=g}g$
Доказательство. Отображение $f:g \to g^{-1}$ - автоморфизм коммутативной группы, его порядок равен 2. Значит $G$ разбивается на 3 множества: множество $A_0 = \{g: f(g)=g \}$, которое $f$ переводит в себя $f(A_0)=A_0$ и 2 класса $A_+$ и $A_-$ таких, что если $g \in A_+$, то $f(g)=g^{-1} \in A_-$ и наоборот.
Тогда

$$\prod\limits_{g \in G}g = \prod\limits_{g \in A_0}g \cdot \prod\limits_{g \in A_+}g \cdot \prod\limits_{g \in A_-}g = \prod\limits_{g \in A_0}g \cdot \prod\limits_{g \in A_+}g \cdot \prod\limits_{g \in A_+}g^{-1} = \prod\limits_{g \in G, g^{-1}=g}g$$

Теперь берем $G=\mathbb{Z}^*_{p^m}$. В ней $a^{-1}=a \Leftrightarrow a = \pm 1$, и тогда

$$1 \cdot ... \cdot (p-1) \cdot (p+1)...\cdot (2p-1).... (p^m-p+1) \cdot ... \cdot (p^m-1) = -1 \cdot 1 = -1 \pmod {p^m}$$

Вот и пробуйте использовать эту формулу для вычисления остатка по модулю $p^m$, только предварительно сократить на числа, кратные $p$ все равно придется + от сокращений еще кое-что останется (произведение биномиальных коэффициентов).

[malphunction]

Нашел подходящую публикацию: вычисление биномиального коэффициента по модулю степени простого числа (http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf)

Но с ней тоже возникли проблемы, перенес обсуждение сюда: post438183.html

[Sonic86]

Я Вам там ответил, но лучше пишите здесь, темы дублировать нехорошо