ACMP 555

Ссылка на задачу

• 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.