Codeforces Round 863 (Div. 3) |
---|
Закончено |
Это сложная версия задачи, она отличается от простой только ограничениями на $$$n$$$ и $$$k$$$.
Влад нашёл ряд из $$$n$$$ плиток и число $$$k$$$. Плитки пронумерованы слева направо и $$$i$$$-я плитка имеет цвет $$$c_i$$$. Немного подумав, он решил, что с этим делать.
Вы можете начать с любой плитки и прыгать на любое количество плиток вправо, формируя при этом путь $$$p$$$. Назовём путь $$$p$$$ длины $$$m$$$ правильным, если верно:
Ваша задача найти количество правильных путей максимальной длины. Так как это число может оказаться слишком большим, выведите его по модулю $$$10^9 + 7$$$.
Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 5000$$$) — количество плиток в ряду и длину блока.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвета плиток.
Гарантируется, что сумма $$$n^2$$$ по всем наборам не превосходит $$$25 \cdot 10^6$$$.
Выведите $$$t$$$ чисел, каждое из которых является ответом на соответствующий набор входных данных — количество правильных путей максимальной длины по модулю $$$10^9 + 7$$$.
55 21 2 3 4 57 21 3 1 3 3 1 311 41 1 1 1 1 1 1 1 1 1 15 21 1 2 2 25 11 2 3 4 5
1 4 165 3 1
В первом примере невозможно составить правильный путь, длины больше $$$0$$$.
Во втором примере нас интересуют следующие пути:
В третьем примере подходит любой путь длины $$$8$$$.
Название |
---|