4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс, Актобе


Задача 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. $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
  2. $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
  3. $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
  4. $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.
Пример:
Вход
3 1
2
1
2
2
Ответ
4
Замечание
$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка. В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$. ( Nurlykhan Kairly )
посмотреть в олимпиаде

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

  0
2020-10-22 19:03:31.0 #

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

  0
2021-04-30 12:29:53.0 #

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