Подскажите, пожалуйста, как работает предпосчёт факториалов с помощью которого считается кол-во размещений по модулю, встретился с этим на atcoder G25 и у многих одинаковый код(как на скриншоте), не понимаю что в нём происходит.
Есть другой вариант подсчёта invfactorial — с помощью быстрого возведения в степень(https://agc025.contest.atcoder.jp/submissions/2611599), но почему invfactorial[2] = fact[2] ^ (MOD — 2) тоже вообще не ясно.
https://agc025.contest.atcoder.jp/submissions/2607571 посылка, которая должна была быть на скриншоте, который не прикрепляется
подсчёт обратных с объяснением что тут происходит
Тот факт, что invfactorial[2] = fact[2] ^ (MOD — 2) следует из малой теоремы Ферма:
по МТФ a^(MOD — 1) = 1 => a^(MOD — 2) = a^(-1).
Там просто человек считает отдельно по модулю значения
, 
... 
.
, 
... 
. Точно так же, как предподсчитывают обычный факториал по модулю.
Затем он их перемножает и получает
Другое дело, посчитать обратное значение по модулю можно двумя способами.
Эта формула для составных m плохо работает — ничто не мешает
m % nбыть не взаимно простым с m, даже если n взаимно просто с m (20 % 3 = 2). Её основное преимущество в том, что она асимптотически быстрее считает обратные для первых n чисел по сравнению с n возведениями в степень (а также код короче, если возведение в степень не оказалось нужно по какой-то другой причине).Дай вам бог здоровья и много рейтинга!