Областная олимпиада по информатике 2019 год
Задача C. Хан и массив
Ограничение по времени:
2 секунды
Ограничение по памяти:
512 мегабайт
Хан на день рождения получил массив из n элементов. И начал с ним играться. Он взял каждый элемент и записал m раз. Также у Хана есть любимое простое число P. Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на P. Помогите Хану узнать сколько таких подпоследовательностей.
Формат входного файла
В первой строке даны три целых числа n, m, P через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно (1<=n<=105,1<=m<=109,1<=P<=103).
Во второй строке даны n целых чисел a1,a2,...,an — полученный Ханом массив на его день рождения (1<=ai<=109).
Формат выходного файла
Выведите одно число — количество подпоследовательностей, которые в сумме делятся на P. Так как это число может быть большим, выведите его остаток от деления на 1000000007.
Система оценки
Подзадача 1 (10 баллов) — n<=105, m<=105, P=2.
Подзадача 2 (10 баллов) — n∗m<=20, P<=1000.
Подзадача 3 (10 баллов) — n∗m∗P<=106,.
Подзадача 4 (20 баллов) — n∗m<=250000, P<=500.
Подзадача 5 (50 баллов) — n<=105, m<=109, P<=1000.
Пример:
Вход 3 2 5 3 7 4Ответ
11
Замечание
Хан преобразует изначальный массив следующим образом. Пусть a1,a2,...,an будет изначальным массивом. И заведем пустой массив b. Один за одним, слева направо будем обрабатывать элементы массива a и элемент ai припишем к b ровно m раз. Хан будет решать задачу над полученным массивом b.
Подпоследовательность — последовательность, которая получается путем удаления нескольких, возможно ноль, элементов изначальной последовательности.
В первом примере, массив b будет выглядеть следующим образом: 3,3,7,7,4,4. Вот все 11 подпоследовательности, сумма которых делится на 5: [3,7], [3,7], [3,7], [3,7], [3,3,4], [3,3,4], [3,3,7,7], [7,4,4], [7,4,4],[3, 7, 7, 4, 4], [3,7,7,4,4].
(
Nurdaulet Akhanov
)
Комментарий/решение:
import itertools
input = open("test_in.txt", "r")
output = open("test_out.txt", "w")
⠀
n,m,p = map(int, input.readline().split())
a = input.readline().split()
b = []
q = 0
⠀
for i in a:
⠀⠀⠀⠀for r in range(m):
⠀⠀⠀⠀⠀⠀⠀b.append(int(i))
⠀
for L in range(1, len(b)+1):
⠀for k in itertools.combinations(b, L):
⠀⠀⠀if sum(k)%5==0:
⠀⠀⠀⠀⠀⠀⠀q+=1
⠀⠀⠀⠀⠀⠀⠀#print(k) 5-ке бөлінетін комбинацияларды шығару үшін
⠀
output.write(str(q))
input.close()
output.close()
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.