Произведение произведений элементов всех подпоследовательностей длины k массива
Мне дали массив длины N. Я должен найти произведение произведений элементов всех подпоследовательностей длины К.
Например,
Array -> [1,2,3,4] N= 4,К= 2
Подпоследовательности -> {1,2} {1,3} {1,4} {2,3} {2,4} {3,4}
Продукты -> 2 3 4 6 8 12
Продукт из продуктов 2 * 3 * 4 * 6 * 8 * 12 = 13824
Это можно сделать легко, если N & К небольшие, но я не могу получить результат, когда 1<= п<= 2000, 1<= к<= п. Ответ может быть слишком большим, поэтому мы можем дать ответ по модулю 1000000007. Может кто-нибудь сказать мне, как это сделать для большого N & К?
Решение
Больше подсказок:
Маленькая теорема Ферма утверждает (с ^ обозначает объяснение)
n^(p-1) ≡ 1 (mod p) для всех премьер p а также n взаимно с p,
Следовательно, n^x ≡ n^(x mod (p-1)) (mod p)
Теперь используйте треугольник Паскаля или все, что может помочь вычислению x mod (p-1),
Другие решения
Продукт продуктов означает то же, что и продукт: (a_1 * a_2) * (a_3 * a_4) = a_1 * a_2 * a_3 * a_4.
Произведение произведений подпоследовательностей можно эффективно рассчитать с помощью мощности: (a_1 * a_2) * (a_1 * a_3) * (a_2 * a_3) = a_1 * a_1 * a_2 * a_2 * a_3 * a_3 = a_1 ** 2 * a_2 ** 2 * a_3 ** 2
найти n количество подпоследовательностей, содержащих первый элемент. Затем рассчитайте каждый элемент (a_i ** n = a'_i) к власти n, Затем рассчитайте произведение всех a'_i,
Также для (a * a * a)% b = (((((a * a)% b) * a)% b)
а также
(a * b)% c = ((a% c) * (b% c))% c