Рассчитано nCr mod m (n выберите r) для больших значений n (10^9)
Теперь, когда CodeSprint 3 закончен, мне стало интересно, как решить эту проблему. Нам нужно просто вычислить nCr mod 142857 для больших значений r и n (0<=n<=10^9; 0<=r<=n). Я использовал рекурсивный метод, который проходит мин (r, nr) итераций, чтобы вычислить комбинацию. Оказывается, это было недостаточно эффективно. Я пробовал несколько разных методов, но все они, кажется, недостаточно эффективны. Какие-либо предложения?
1 ответ
Для не простого мода, разложите его (142857 = 3^3 * 11 * 13 * 37) и вычислите C(n,k) mod p^q для каждого простого множителя мода, используя общую теорему Лукаса, и объедините их, используя Китайская теорема об остатках.
Например, C(234, 44) mod 142857 = 6084, затем
- С (234, 44) мод 3^3 = 9
- С (234, 44) мод 11 = 1
- С (234, 44) мод 13 = 0
- С (234, 44) мод 37 = 16
Китайская теорема об остатках включает в себя нахождение х такой
- х = 9 мод 3 ^ 3
- х = 1 мод 11
- х = 0 мод 13
- х = 16 мод 37
Результат х = 6084.
пример
С (234, 44) мод 3 ^ 3
Сначала преобразуйте n, k и nk в основание p
n = 234_10 = 22200_3
k = 44_10 = 1122_3
r = nk = 190_10 = 21001_3
Далее найдите количество переносов
e[i] = number of carries from i to end
e 4 3 2 1 0
1 1
r 2 1 0 0 1
k 1 1 2 2
n 2 2 2 0 0
Теперь создайте факториальную функцию, необходимую для генерала Лукаса
def f(n, p):
r = 1
for i in range(1, n+1):
if i % p != 0:
r *= i
return r
Поскольку q = 3, вы будете рассматривать только три цифры базового представления p за раз
Так
f(222_3, 3)/[f(210_3, 3) * f(011_3, 3)] *
f(220_3, 3)/[f(100_3, 3) * f(112_3, 3)] *
f(200_3, 3)/[f(001_3, 3) * f(122_3, 3)] = 6719344775 / 7
Сейчас
s = 1 if p = 2 and q >= 3 else -1
затем
p^e[0] * s * 6719344775 / 7 mod 3^3
e[0] = 2
p^e[0] = 3^2 = 9
s = -1
p^e[0] * s * 6719344775 = -60474102975
Теперь у вас есть
-60474102975 / 7 mod 3^3
Это линейное сравнение и может быть решено с помощью
ModularInverse(7, 3^3) = 4
4 * -60474102975 mod 27 = 9
Следовательно, C(234, 44) mod 3^3 = 9