Есть ли простой способ реализовать !n mod p (количество нарушений)) where n ≤ 2∗10^8 и p - это простое и p < 1000
Программа должна выполняться быстро, поэтому наивный подход не работает.
Субфакториально по модулю простого (! n mod p)
Ответ 1
Оказывается, что !n mod p является периодическим с периодом 2p. Таким образом, мы можем вычислить !n mod p как !(n mod 2p) mod p, что мы делаем с рекурсивной формулой для расстройств !n = (n-1) (!(n-1) + !(n-2)).
Для доказательства:
- Заметим, что
!(p+1) = 0 mod p, рекурсивным соотношением для нарушений. - Работаем по модулю p,
!(n+p) = !p * !n(это можно доказать индуктивно, используя предыдущее наблюдение). - Заметим, что
!p = -1 mod p. Википедия дает формулу:!n = n! - Sum[(n choose i) * !(n-i), i=1..n]- по модулю p, единственный ненулевой член в правой части появляется гдеi=n. - Завершите, что
!(n+2p) = !p !p !n = !n mod p.
Из доказательства видно, что мы можем фактически вычислить !n = ± !(n mod p) mod p, где знак положителен, когда n mod 2p меньше p.
Ответ 2
Имея рекурсивную формулу (!n = (n - 1) (!(n-1) + !(n-2))), почему бы не реализовать операции "умножение по модулю p" и "дополнение по модулю p"?