시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
В лаборатории искусственного интеллекта разработали новый метод машинного обучения. В процессе обучения программы используется n итераций. Каждая итерация заключается в том, что обучаемая программа запускается на некотором обучающем наборе.
Были подготовлены обучающие наборы сложности от 0 до k. План обучения задаётся массивом целых чисел [a1, a2, . . . , an], где ai задаёт сложность набора, используемого на i-й итерации обучения. Для всех i от 1 до n должно выполняться неравенство 0 ⩽ ai ⩽ k.
Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений i и j, где 1 ⩽ i < j ⩽ n, выполнялось (ai and aj) = ai. Напомним, что побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если у обоих аргументов он равен 1. Например, (14 and 7) = (11102 and 01112) = 1102 = 6. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «&», в Паскале как «and».
Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами li и ri и означает, что ali ≠ ari.
Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 109 + 7.
Требуется написать программу, которая по заданным целым числам n и k, а также m требованиям вида li, ri определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 109 + 7.
Первая строка входных данных содержит три целых числа n, m и k — количество итераций обучения, количество требований и максимальную сложность обучающего набора (1 ⩽ n ⩽ 3 · 105, 0 ⩽ m ⩽ 3 · 105, 0 ⩽ k ⩽ 1018).
Следующие m строк описывают требования, i-я строка содержит два целых числа li, ri, которые означают, что ali ≠ ari (1 ⩽ li < ri ⩽ n). Гарантируется, что все требования различны.
Выведите одно целое число — остаток от деления количества эффективных планов, удовлетворяющих всем требованям, на число 109 + 7.
번호 | 배점 | 제한 |
---|---|---|
1 | 8 | 1 ⩽ n ⩽ 500 m = 0 0 ⩽ k ⩽ 500 |
2 | 20 | 1 ⩽ n ⩽ 3 · 105 m = 0 0 ⩽ k ⩽ 107 |
3 | 10 | 1 ⩽ n ⩽ 3 · 105 m = 0 0 ⩽ k ⩽ 1018 |
4 | 8 | 1 ⩽ n ⩽ 50 0 ⩽ m ⩽ 50 0 ⩽ k ⩽ 50 |
5 | 16 | 1 ⩽ n ⩽ 2000 0 ⩽ m ⩽ 2000 0 ⩽ k ⩽ 107 |
6 | 6 | 1 ⩽ n ⩽ 2000 0 ⩽ m ⩽ 2000 0 ⩽ k ⩽ 1018 |
7 | 10 | 1 ⩽ n ⩽ 3 · 105 0 ⩽ m ⩽ 200 0 ⩽ k ⩽ 107 |
8 | 6 | 1 ⩽ n ⩽ 3 · 105 0 ⩽ m ⩽ 200 0 ⩽ k ⩽ 1018 |
9 | 16 | 1 ⩽ n ⩽ 3 · 105 0 ⩽ m ⩽ 3 · 105 0 ⩽ k ⩽ 1018 |
2 0 3
9
3 1 2 1 2
2
Все возможные планы для первого теста: [0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 3], [2, 2], [2, 3], [3, 3]. Для второго теста: [0, 1, 1], [0, 2, 2].
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2019 4번