(i, j), где i < j, но a[i] > a[j].
Дано число n и список правил rules, где rules[t] = [end, cnt] означает: в префиксе перестановки с индексами от 0 до end включительно ровно cnt инверсий.
Сколько существует перестановок чисел 0, 1, ..., n - 1, удовлетворяющих всем правилам сразу? Ответ верните по модулю 10⁹ + 7.n=3, rules=[[2, 1]] → 2
Ровно одна инверсия во всей перестановке бывает у [1, 0, 2] и [0, 2, 1].
n=4, rules=[[3, 3], [1, 0]] → 3
Первые два элемента идут по возрастанию, а всего инверсий три. Так устроены ровно три перестановки: [0, 3, 2, 1], [1, 2, 3, 0] и [1, 3, 0, 2].
n=3, rules=[[0, 1], [2, 1]] → 0
В префиксе из одного элемента инверсий не бывает, поэтому подходящих перестановок нет.
end различны, и среди них есть n - 1n=3, rules=[[2, 1]]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 87 тестов на сервере, включая скрытые.