CF1811G2 Vlad and the Nice Paths (hard version)

这是该问题的困难版本，与简单版本的区别仅在于 $n$ 和 $k$ 的约束条件。 Vlad 发现了一排 $n$ 块瓷砖以及一个整数 $k$。这些瓷砖从左到右编号，第 $i$ 块瓷砖的颜色为 $c_i$。经过一番思考，他决定对这些瓷砖进行如下操作。 你可以从任意一块瓷砖开始，向右跳任意数量的瓷砖，形成一条路径 $p$。我们称长度为 $m$ 的路径 $p$ 是“优美的”，当且仅当： - $p$ 可以被划分为若干长度恰好为 $k$ 的块，即 $m$ 能被 $k$ 整除； - $c_{p_1} = c_{p_2} = \ldots = c_{p_k}$； - $c_{p_{k+1}} = c_{p_{k+2}} = \ldots = c_{p_{2k}}$； - $\ldots$ - $c_{p_{m-k+1}} = c_{p_{m-k+2}} = \ldots = c_{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, \dots, c_n$（$1 \le c_i \le n$），表示每块瓷砖的颜色。 保证所有测试用例中 $n^2$ 的总和不超过 $25 \cdot 10^6$。

输出 $t$ 行，每行一个数，表示对应测试用例最大长度优美路径的数量，对 $10^9 + 7$ 取模。

在第一个样例中，不可能构造出长度大于 $0$ 的优美路径。 在第二个样例中，满足条件的路径有： - $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ - $2 \rightarrow 4 \rightarrow 5 \rightarrow 7$ - $1 \rightarrow 3 \rightarrow 5 \rightarrow 7$ - $1 \rightarrow 3 \rightarrow 4 \rightarrow 7$ 在第三个样例中，任意长度为 $8$ 的路径都是优美的。 由 ChatGPT 4.1 翻译