Nurlykhan Kairly

Задача №1.

Задача B. Array

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Дан массив

$a$ длины

$k$ . Так же, имеются

$n$ массивов длины

$k$ . Массив

$x$ называется хорошим, если существует перестановка

$p$ длины

$k$ , такая что для каждого

$i$

$(1 <= i <= k)$ выполняется

$x_{p_i} \equiv 0 \pmod{a_i}$ . Вам необходимо посчитать количество пар

$(l, r)$

$(1 <= l <= r <= n)$ , таких что количество хороших массивов в отрезке больше чем нехороших.

Формат входного файла

В первой строке входных данных даются числа

$n$ и

$k$

$(1 <= n <= 10^5, 1 <= k <= 20)$ . Во второй строке входных данных даётся массив

$a$ длины

$k$

$(1 <= a_i <= 10^9)$ . В следующих

$n$ строк даются массивы длины

$k$ , где в

$i$ -ой содержится массив

$b_i$

$(1 <= b_{ij} <= 10^9,$ где

$1 <= i <= k)$ .

Формат выходного файла

В единственной строке выходных данных выведите одно число - ответ на задачу.

Система оценки

Данная задача содержит четыре подзадачи:

$1 <= n <= 1000, k = 1$ . Оценивается в $15$ баллов.
$1 <= n <= 1000, 1 <= k <= 8$ . Оценивается в $19$ баллов.
$1 <= n <= 100, 1 <= k <= 20$ . Оценивается в $31$ баллов.
$1 <= n <= 10^5, 1 <= k <= 8$ . Оценивается в $35$ баллов.

Пример:

Вход

Ответ

Замечание

$a \equiv 0 \pmod{b}$ - означает что число

$a$ делится на

$b$ без остатка. В первом тестовом примере, пары

$(1, 1)$ и

$(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно

$0$

$(0 <= 1)$ , а во втором равно

$1$

$(1 <= 1)$ . ( Nurlykhan Kairly )
комментарий/решение(2) олимпиада

Задача №2.

Задача B. Array

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Дан массив

$a$ длины

$k$ . Так же, имеются

$n$ массивов длины

$k$ . Массив

$x$ называется хорошим, если существует перестановка

$p$ длины

$k$ , такая что для каждого

$i$

$(1 <= i <= k)$ выполняется

$x_{p_i} \equiv 0 \pmod{a_i}$ . Вам необходимо посчитать количество пар

$(l, r)$

$(1 <= l <= r <= n)$ , таких что количество хороших массивов в отрезке больше чем нехороших.

Формат входного файла

В первой строке входных данных даются числа

$n$ и

$k$

$(1 <= n <= 10^5, 1 <= k <= 20)$ . Во второй строке входных данных даётся массив

$a$ длины

$k$

$(1 <= a_i <= 10^9)$ . В следующих

$n$ строк даются массивы длины

$k$ , где в

$i$ -ой содержится массив

$b_i$

$(1 <= b_{ij} <= 10^9,$ где

$1 <= i <= k)$ .

Формат выходного файла

В единственной строке выходных данных выведите одно число - ответ на задачу.

Система оценки

Данная задача содержит четыре подзадачи:

$1 <= n <= 1000, k = 1$ . Оценивается в $15$ баллов.
$1 <= n <= 1000, 1 <= k <= 8$ . Оценивается в $19$ баллов.
$1 <= n <= 100, 1 <= k <= 20$ . Оценивается в $31$ баллов.
$1 <= n <= 10^5, 1 <= k <= 8$ . Оценивается в $35$ баллов.

Пример:

Вход

Ответ

Замечание

$a \equiv 0 \pmod{b}$ - означает что число

$a$ делится на

$b$ без остатка. В первом тестовом примере, пары

$(1, 1)$ и

$(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно

$0$

$(0 <= 1)$ , а во втором равно

$1$

$(1 <= 1)$ . ( Nurlykhan Kairly )
комментарий/решение(2) олимпиада