как получить модуль значения в экспоненциальной форме

Я не уверен, что это действительно возможно и правильно, но позвольте мне обобщить мои комментарии и расширить ответ Мики Динеску.

Как уже писал Мики:

a × b ≣_m a_m × b_m

Вы можете использовать это в своем равенстве:

90! / 10!^9 ≣_м х

Вычислите каждый член:

90!_м / 10!^9_м ≣_м х

Затем найдите свой обратный мультипликатив от 10!^9_m. Затем умножьте обратное значение на 90!_m.

update Это кажется правильным (по крайней мере, для этого случая :)). Я проверил с вольфрамом:

(90!/10!^9) mod (10^9+7) = 998551163

Это приводит к тому же результату:

90! mod (10^9+7) = 749079870
10!^9 mod (10^9+7) = 220052161

сделать обратное:

(220052161 * x) mod(10^9+7) = 1 = 23963055

потом:

(749079870*23963055) мод (10^9+7) = 998551163

Никаких доказательств, но некоторые доказательства того, что это может сработать :)

Я бы сказал, что способ вычислить общее количество перестановок по модулю m, где m — произвольное целое число (обычно выбираемое как большое простое число), заключается в использовании следующего свойства:

 (a * b) % m = ((a % m) * (b % m)) % m

Учитывая, что общее количество перестановок N равно N! = 1 * 2 * 3 * .. * N, если вам нужно вычислить N! % m, вы можете по существу применить указанное выше свойство для умножения по модулю m, и у вас есть:

 ((((1 * (2 % m)) % m) * (3 % m)) % m) * .. 

ИЗМЕНИТЬ

Чтобы вычислить 90! / (10! ^ 9), вы можете упростить множители, а затем использовать умножение по модулю m для вычисления окончательного результата по модулю m.

Вот что я думаю:

90! = 10! * (11 * 12 * .. * 20) * (21 * 22 * .. * 30) * .. * (81 * 82 * .. * 90)

Затем вы можете переписать исходное выражение как:

(10! * (11 * 12 * .. * 20) * (21 * 22 * .. * 30) * .. * (81 * 82 * .. * 90)) / (10! * 10! * ... * 10!)

В числителе у вас есть произведение 9 множителей, учитывая каждое выражение в скобках как множитель. То же самое верно и для знаменателя (у вас есть 9 множителей, каждый из которых равен 10!).

Первый множитель в знаменателе легко упростить. После этого у вас остается 8 пар, которые нуждаются в упрощении.

Таким образом, вы можете факторизовать каждый член произведений и упростить знаменатель. Например:

11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 <=> 11 * 2 * 2 * 3 * 13 * 2 * 7 * 3 * 5 * 2 * 2 * 2 * 2 * 17 * 2 * 9 * 2 * 2 * 5

Знаменатель всегда будет: 2 * 3 * 2 * 2 * 5 * 2 * 3 * 7 * 2 * 2 * 2 * 2 * 3 * 3 * 2 * 5

После упрощения вторая пара сводится к: 2 * 2 * 11 * 13 * 17 * 19

То же самое можно применить к каждой последующей паре, и вы получите простое произведение, которое можно вычислить по модулю m, используя приведенную выше формулу.

Конечно, эффективная реализация алгоритма для выполнения упрощения будет сложной задачей, поэтому в конечном итоге должен быть лучший способ, который сейчас ускользает от меня.