Nurdaulet Akhanov


Задача №1. 

Задача B. Делимость

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на 8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ.
Формат входного файла
В первой строке дано цело число $n$ $(1 \leq n \leq 10^3) $ - длинна числа. $\\$ Во второй строка дана строка состоящая из цифр $s$ - число которое надо проверить.
Формат выходного файла
Выведите YES если число делится на 8 по правилам ОМЫ иначе NO
Примеры:
Вход
2
23
Ответ
YES
Вход
3
101
Ответ
NO
Замечание
Перестановка числа х - это число, состоящее из тех же цифр, что и х, но в другом порядке. Например, числа, которые можно получить путем перестановки цифр числа 123: 132, 213, 231, 312, 321 В первом примере из числа 23 можно получить делящееся на 8 число 32, ответ YES. Во втором примере из числа 101 невозможно получить число делящееся на 8, ответ NO. $\\$ $\\$ Subtask 1: $(n \leq 100)$ $\\$ Subtask 2: $(n \leq 1000)$ ( Nurdaulet Akhanov )
комментарий/решение(3) олимпиада
Задача №2. 

Задача C. Хан и массив

Ограничение по времени:
2 секунды
Ограничение по памяти:
512 мегабайт

Хан на день рождения получил массив из $n$ элементов. И начал с ним играться. Он взял каждый элемент и записал $m$ раз. Также у Хана есть любимое простое число $P$. Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на $P$. Помогите Хану узнать сколько таких подпоследовательностей.
Формат входного файла
В первой строке даны три целых числа $n$, $m$, $P$ через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Во второй строке даны $n$ целых чисел $a_1, a_2, ..., a_n$ — полученный Ханом массив на его день рождения $(1 <= a_i <= 10^9)$.
Формат выходного файла
Выведите одно число — количество подпоследовательностей, которые в сумме делятся на $P$. Так как это число может быть большим, выведите его остаток от деления на $1000000007$.
Система оценки
Подзадача 1 (10 баллов) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. Подзадача 2 (10 баллов) — $ n * m <= 20$, $P <= 1000 $. Подзадача 3 (10 баллов) — $ n * m * P <= 10^6, $. Подзадача 4 (20 баллов) — $ n * m <= 250000$, $P <= 500 $. Подзадача 5 (50 баллов) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $.
Пример:
Вход
3 2 5
3 7 4
Ответ
11
Замечание
Хан преобразует изначальный массив следующим образом. Пусть $a_1, a_2, ..., a_n$ будет изначальным массивом. И заведем пустой массив $b$. Один за одним, слева направо будем обрабатывать элементы массива $a$ и элемент $a_i$ припишем к $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 )
комментарий/решение олимпиада
Задача №3. 

Задача C. Хан и массив

Ограничение по времени:
2 секунды
Ограничение по памяти:
512 мегабайт

Хан на день рождения получил массив из $n$ элементов. И начал с ним играться. Он взял каждый элемент и записал $m$ раз. Также у Хана есть любимое простое число $P$. Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на $P$. Помогите Хану узнать сколько таких подпоследовательностей.
Формат входного файла
В первой строке даны три целых числа $n$, $m$, $P$ через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Во второй строке даны $n$ целых чисел $a_1, a_2, ..., a_n$ — полученный Ханом массив на его день рождения $(1 <= a_i <= 10^9)$.
Формат выходного файла
Выведите одно число — количество подпоследовательностей, которые в сумме делятся на $P$. Так как это число может быть большим, выведите его остаток от деления на $1000000007$.
Система оценки
Подзадача 1 (10 баллов) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. Подзадача 2 (10 баллов) — $ n * m <= 20$, $P <= 1000 $. Подзадача 3 (10 баллов) — $ n * m * P <= 10^6, $. Подзадача 4 (20 баллов) — $ n * m <= 250000$, $P <= 500 $. Подзадача 5 (50 баллов) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $.
Пример:
Вход
3 2 5
3 7 4
Ответ
11
Замечание
Хан преобразует изначальный массив следующим образом. Пусть $a_1, a_2, ..., a_n$ будет изначальным массивом. И заведем пустой массив $b$. Один за одним, слева направо будем обрабатывать элементы массива $a$ и элемент $a_i$ припишем к $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 )
комментарий/решение олимпиада