Вычислить модуль перестановок повторяющихся целых чисел

Я хочу рассчитать Ps mod K, где Ps – это общее количество уникальных перестановок элементов. в наборе S. Проблема в том, что набор S может иметь повторения, поэтому Ps = n! / (f1!f2! ... fn!), где n - количество элементов, а знаменатель - произведение факториала частот каждого элемента в S.

Целое число n можно считать значительно большим, скажем, около 10^6, и вряд ли оно поместится в uint64_t. Возможно ли вычислить Ps mod K, не прибегая к библиотеке произвольной точности? Если да, есть ли какие-нибудь быстрые методы для его расчета?


algorithm modular-arithmetic
person Methusael Murmu    schedule 03.10.2015    source источник
comment
Кстати, 10^6 вписывается в uint64_t.   -  person Jeremy West    schedule 04.10.2015
comment
Или вы имели в виду, что n! не помещается в uint64_t?   -  person Jeremy West    schedule 04.10.2015
comment
Да, n! не подходит.   -  person Methusael Murmu    schedule 04.10.2015
comment
кстати. если n около 10^6!, то Ps mod K в большинстве случаев будет равно 0, если только K не очень велико.   -  person SpiderPig    schedule 04.10.2015
comment
Я предполагаю, что k тоже не обязательно простое число?   -  person Jeremy West    schedule 04.10.2015
comment
Да, это так. Я решал проблему программирования, которая вынудила меня к этому. Проблема указывает K = 10^9+7.   -  person Methusael Murmu    schedule 04.10.2015

Ответы (3)


arrow_upward
6
arrow_downward

Рассмотрим в качестве примера 9!/(4!3!2!). Это

9.8.7.6   5.4.3   2.1
------- x ----- x ---
4.3.2.1   3.2.1   2.1

Другими словами, это произведение трех биномиальных коэффициентов 9C4 x 5C3 x 2C2. Таким образом, вы всегда сможете свести его к произведению биномиальных коэффициентов. Вам нужно вычислить эти биномиальные коэффициенты по модулю K и умножить ответы по модулю K.

Итак, вам нужен эффективный способ вычисления биномиальных коэффициентов по модулю K.

Я не знаю, насколько это возможно для n == 10^6, но здесь приведен метод эффективного расчета биномиальных коэффициентов по модулю K:

https://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/

person Paul Boddington    schedule 04.10.2015
comment
Это точное наблюдение! Я собираюсь прочитать эту статью. Я вернусь, как только у меня будет рабочая реализация. - person Methusael Murmu; 04.10.2015
comment
@MethusaelMurmu Удачи. Я думаю, что это будет довольно сложно - я бы провел подробный поиск, чтобы узнать, делает ли это уже библиотека. - person Paul Boddington; 04.10.2015
comment
Ссылка на блог обновлена: fishi.devtail.io/weblog/2015/06/25/ - person fishi0x01; 13.01.2019

arrow_upward
0
arrow_downward

Если вы хотите рассчитать, например. n!modK, вам не нужно сначала вычислять n!. Вместо этого вы можете сделать цикл, который выглядит следующим образом.

result = 1
for(i = 2; i <= n; i++) {
  result = (result * i) % K
}

Самый простой способ объяснить, почему это работает, — посмотреть, что происходит с последней цифрой числа, когда вы умножаете его на что-то еще. например 1234* 3. Какая последняя цифра результата? Это 2, что равно (4*3)mod10. На последнюю цифру результата влияет только последняя цифра двух факторов. Это справедливо для любой системы счисления. Не только по основанию 10. Поэтому достаточно, чтобы переменная result сохраняла последнюю цифру результата по основанию K.

person SpiderPig    schedule 04.10.2015
comment
Проблема в том, что вопрос предполагает разделение. Если вы знаете, что n!, r! и (n - r)! равны по модулю K, это не говорит вам о значении n!/(r! * (n - r)!) по модулю K, потому что знаменатель может не быть обратимым элементом кольца целых чисел по модулю K. - person Paul Boddington; 04.10.2015

arrow_upward
0
arrow_downward

Если есть необходимость рассчитать Ps mod K для многих значений Ps, то это может быть целесообразно предварительно вычислить n! mod K для всех значений n, которые могут вам понадобиться (если n ≤ 106, то это разумно).

Кроме того, если K простое число, вы можете обрабатывать деление, вместо этого умножая на модуль мультипликативное число, обратное числу, на которое вы хотите разделить. Например, если K=1 000 000 007, то вместо деления на 2 можно умножить на 500 000 004.

Есть несколько способов вычислить его, самый простой из них — вычислить xK-2 mod K (это работает благодаря Маленькая теорема Ферма). Затем вы можете предварительно вычислить модульную мультипликативную инверсию каждого факториала. Затем очень легко вычислить Ps mod K, используя кэшированные значения.

person Ryan Tarpine    schedule 17.08.2020