Задача, на аккуратную реализацию:
- если мы находимся в пункте назначение, то ответ T.
- иначе лифт может находится в 2*М-2 состояниях, которые будут циклично повторятся. Состояние это номер этажа и направление, таких состояний будет 2*М-2. что-бы узнать состояние можно просто взять время по модулю. По состоянию можем определить этаж и направление, для удобства напишем функцию, которая определяет время которое нужно лифту что-бы добраться от одного этажа со стартовым направлением до другого, там нужно рассмотреть 4 варианта, этаж выше/ниже, и направление вверх/вниз. Дальше ответом будет функция от начального положения лифта в момент Т до старта+расстояние от старта до финиша.

Перебираем какое число мы поставим(I) первым оно будет от 1 до min(mod-1,A) потому-что дальше mod перебирать нет смысла, числа по модулю будут повторяться. Дальше домножим наше первое число на (10⁹)%mod и возьмем произведение по модулю, пускай оно будет X тогда число I подходит если X!=0 и X+B<mod, что вроде-бы очевидно.

Тут было много решений с ДФС, но я писал немного другое:
Зафиксируем вершину V и разобьем все вершины на 2 группы, те которые имеют ребра в V и те которые имеют ребра из V. Теперь ребра делятся на такие группы: идут в V(d1), идут из V(d2), лежат в первой группе(m1), лежат во второй группе(m2), выходят из первой во вторую(n1), выходят из второй в первую(n2). Теперь мы можем утверждать что ответ есть если последняя группа не пустая. Как нам посчитать величины групп? Для начала посмотрим на то что мы знаем: по степеням входа и выхода вершин мы знаем значение n1+m1 и n2+m2, так-же мы знаем значение n1+n2 которое очевидно равно произведению этих двух групп, так-как между каждой парой есть ребро. Из этого несложно выразить значение n2,если оно положительное то переберем все пары и проверим их, хотя-бы одна найдется, так-что асимптотика O(N²).

Делать можно разбиением задачи на подзадачи. Для начала заметим что любой отрезок до того как его преобразовали можно задать 2мя числами: 1м числом и разницей между числами, то-есть последовательность ничто другое как арифметическая прогрессия. При разбиении на два отрезка мы из состояния (l,r,q,w) l,r - границы отрезка, q - первое число,w - разница между числами. перейдем в состояния: (l,(l+r)/2,q,w*2) и ((l+r)/2+1,r,q+w,w*2). Теперь если мы попали в отрезок который полностью лежит в той области которая нас интересует, то нам не важно как стоят числа, нам важны сами числа. Суммы можно посчитать обрезав ненужные части как сумму арифметической прогрессии. В ненужных отрезки(которые не имеют общих частей с интересующих) мы просто ходить не будем. А кол-во отрезков будет как при подсчете суммы на отрезке в дереве отрезков, то-есть порядка O(log(N)). Что довольно мало.

Ее не сдавал, но решение придумал. Рассмотрим наш граф, он является деревом + одно ребро, то-есть цикл к вершинам которого прицеплены деревья. Рассмотрим задачу для дерева, сначала посмотрим на связь кол-во включенных вершин и количеством компонент связности: в дереве без выключенных вершин 1 компонента , при каждом добавлении выключенного ребра кол-во компонент увеличивается на 1, то-есть кол-во компонент в дереве это просто 1+кол-во выключенных ребер. То-есть нам каждый раз нужно знать кол-во включенных вершин. Эта задача решается с помощью Heavy-light декомпозиции, в подробности вникать не буду, если знать ее, то решение становится ясным, единственно над чем стоит подумать, это как поддерживать в дереве отрезков кол-во вершин с непарными числами. Теперь что-же делать если у нас есть цикл, все так-же просто у нас путь всегда будет один из: путь по дереву которое "свисает с цикла" решается стандартно, и если начало и конец пути лежать в разных деревьях, то-есть проходит по циклу, это можно решать так: решим задачу для корней деревьев которые содержат наши старт и финиш и старта и финиша, и осталось малая часть: разобраться с циклом. Замечу что лексикографичность(по какую сторону будем идти) выбрать не сложно, там всего максимум 2 варианта, то-есть можно сказать что отрезок на котором мы будем менять цвет мы знаем. Осталось установить закономерность как влияют кол-во выключенных клеток. Замечу что то какие деревья и сколько в них чего нас не интересует, нас интересует только их кол-во и кол-во выключенных ребер в цикле. Сначала если у нас все включены, то от ответа нужно отнять N и добавить 1, потому-что у нас все компоненты объединены, при добавлении выключенного ребра ответ будет увеличиваться на 1, то-есть нам нужно будет еще всего-лишь узнавать кол-во выключенных ребер. Вроде-бы все.

Если-что-то не так, то пишите. Надеюсь вам понятно.