ACMP 555
(перенаправлено с «Интернет-олимпиада 12.11.2005, усложнённый уровень, A»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Для каждого цикла сохраним номера циклов, зависящих от него. В общем случае граф зависимостей представляет собой лес. Если мы сумеем вычислить, сколько раз выполнялся (с учётом зависящих циклов) корневой цикл каждой компоненты, то произведение этих значений даст ответ.
Будем поддерживать динамику d[i][from] — сколько раз i-й цикл учитывается в ответе, имея переменную >= from. Для from > r[i] значения d[i][from] равны 0. Для 0 <= from <= r[i] значения d[i][from] = Π + d[i][from + 1], где Π — произведение d[j][from] для всех циклов j, зависящих от i.