Loading [MathJax]/jax/output/SVG/jax.js

Областная олимпиада по информатике 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 баллов) — nm<=20, P<=1000. Подзадача 3 (10 баллов) — nmP<=106,. Подзадача 4 (20 баллов) — nm<=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 )
посмотреть в олимпиаде

Комментарий/решение:

  0
4 года назад #

показать/скрыть код

C++

пред. Правка 3   0
4 года назад #

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()