Задачник Базовый курс EN

Цепочки рейсов

подсчёт вариантов граф матрица разделяй и властвуй предподсчёт олимпиады

Между n аэропортами летают рейсы. Из аэропорта a в аэропорт b их может быть несколько — разные позывные, и каждый считается отдельным способом сделать этот перелёт. Цепочка — последовательность из ровно k рейсов, где каждый следующий вылетает оттуда, куда прилетел предыдущий; аэропорты в цепочке могут повторяться.

Ответьте на q вопросов: сколько цепочек из ровно k рейсов ведут из s в t? Числа огромные, поэтому выведите остаток от деления на 10⁹ + 7.

Во втором примере — настоящая сеть рейсов между 21 аэропортом (база позывных Virtual Radar Server, CC0, снимок 10.10.2026), аэропорт 1 — Алматы, 5 — Астана.

Вход

В первой строке n и m (1 ≤ n ≤ 30, 0 ≤ m ≤ n²). Дальше m строк a b c: из a в b летают c позывных (1 ≤ c ≤ 10⁹); одна пара может встретиться несколько раз — позывные складываются, рейс может вести и в тот же аэропорт. Затем q (1 ≤ q ≤ 200) и q строк s t k (0 ≤ k ≤ 10¹⁸).

Выход

Для каждого вопроса — число цепочек по модулю 10⁹ + 7. При k = 0 цепочка пустая: ответ 1, если s = t, и 0 иначе.

Примеры

Пример 1

Вход

Выход

2
2
0

Пример 2

Вход

21 108
1 2 1
1 3 1
1 5 72
1 6 5
1 7 2
1 8 2
1 9 23
1 10 6
1 11 3
1 12 14
1 13 11
1 14 9
1 15 8
1 16 8
1 17 8
1 18 20
1 19 14
1 20 9
1 21 7
2 1 1
3 1 1
4 5 2
5 1 75
5 4 2
5 7 1
5 8 3
5 9 17
5 10 1
5 11 1
5 13 7
5 14 4
5 15 8
5 16 4
5 17 3
5 18 8
5 19 7
5 20 7
5 21 7
6 1 5
6 18 1
7 1 2
7 5 1
7 9 1
8 1 2
8 5 4
8 20 1
8 21 1
9 1 24
9 5 25
9 6 1
9 7 1
9 12 1
9 15 3
9 16 1
9 17 2
9 18 3
9 19 1
9 20 2
9 21 2
10 1 6
10 5 1
10 21 1
11 1 3
11 5 1
12 1 15
12 9 1
13 1 11
13 5 7
13 19 1
14 1 8
14 5 3
14 18 3
14 19 1
15 1 8
15 5 7
15 9 3
16 1 8
16 5 4
16 9 2
17 1 7
17 5 4
17 9 2
18 1 21
18 5 8
18 6 1
18 9 5
18 14 3
18 19 11
18 20 2
19 1 14
19 5 6
19 9 2
19 13 1
19 14 2
19 18 10
19 20 1
20 1 9
20 5 9
20 8 1
20 9 2
20 18 1
20 19 1
21 1 6
21 5 7
21 8 1
21 9 1
21 10 1
21 20 2
5
1 5 1
1 5 2
1 1 2
1 5 10
1 1 1000000000000000000

Выход

Ограничения

Время · Python: 6000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Сколько цепочек из двух рейсов ведёт из s в t? Переберите аэропорт пересадки и посмотрите, на что похожа получившаяся сумма.

2Подсказка 2

Ответ на вопрос — элемент матрицы C^k, и её можно возвести в степень меньше чем за 120 произведений. Но вопросов двести. Нужна ли для каждого вопроса вся матрица?

3Идея

По утверждению из статьи число цепочек — (C^k)_st, где C_ab — число позывных из a в b. Возводить C в степень заново для каждого вопроса — это около 200 · 90 произведений по n³ умножений, слишком много для Python. Но степени двойки C, C², C⁴, …, C^2⁵⁹ не зависят от вопроса: посчитаем их один раз. А для вопроса нужна одна строка C^k: начнём с вектора, где единица стоит в s, и умножим его на те степени двойки, чьи биты есть в k. Вектор на матрицу — n², а не n³.

4Разбор

Складываем позывные в матрицу по модулю. Предподсчёт: 59 возведений в квадрат. Вопрос: вектор e_s, проход по битам k от младшего: если бит установлен, вектор умножаем на соответствующую степень. Умножения матриц переставлять нельзя, но здесь все множители — степени одной матрицы C, а они друг с другом перестановочны, так что порядок битов неважен. Ответ — координата t вектора.

Во втором примере видно, как растут числа: из Алматы в Астану двумя рейсами — 1192 цепочки, а десятью — 38 516 548 485 362 965 772, это уже больше, чем помещается в 64 бита; поэтому остаток берут после каждого умножения.

4+Решение

5Сложность

Предподсчёт — 60·n³ ≈ 1,6·10⁶ умножений, каждый вопрос — не больше 60·n², все вопросы — около 10⁷. Наивное возведение на каждый вопрос — 200·90·n³ ≈ 5·10⁸.

6Типичные ошибки

Степень заново на каждый вопрос. Верно, но в десятки раз медленнее: шестой тест не укладывается во время на Python.
Переполнение. Произведение двух остатков — до 10¹⁸, сумма тридцати таких — больше 2⁶³. В Go и C++ остаток надо брать после каждого слагаемого.
Повторяющиеся пары. Две строки с одной парой a, b — это сумма позывных, а не замена.
k = 0. Пустая цепочка — одна, из аэропорта в него же.

Алгоритмы задачи

NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи NUM Алгоритм Быстрое возведение в степень aⁿ за O(log n) умножений: квадраты по битам показателя. O(log n) умножений 2 задачи