P13945 [EC Final 2019] King

众所周知，$\textit{Pang}$ 的论文数量呈指数增长。因此，我们对 $\textit{King}$ 序列产生了好奇。 给定一个质数 $p$。当且仅当存在一个整数 $1\leq q < p$，使得对于所有整数 $i\in [2,n]$，都有 $q a_{i-1} \equiv a_i \pmod p$，则序列 $(a_1,a_2,\ldots,a_n)$ 被称为 $\textit{King}$ 序列。 给定一个序列 $B=(b_1,\ldots,b_m)$，请问 $B$ 的最长 $\textit{King}$ 子序列的长度是多少？ 子序列指的是从原序列中删除若干元素（可以为零），且不改变剩余元素的相对顺序后得到的序列。 $Pang$ 最近非常忙，所以他只关心答案是否大于等于 $\frac{n}{2}$。 如果最长 $\textit{King}$ 序列的长度小于 $\frac{n}{2}$，输出 $-1$。否则，输出最长 $\textit{King}$ 子序列的长度。

第一行包含一个整数 $T$，表示测试用例的数量（$1\le T\le 1000$）。 每个测试用例的第一行包含两个整数 $n$ 和 $p$（$2\le n \le 200000$，$2\le p \le 1000000007$，$p$ 为质数）。所有测试用例中 $n$ 的总和不超过 $200000$。 每个测试用例的第二行包含一个长度为 $n$ 的序列 $b_1,\ldots, b_n$（$1\le b_i< p$）。

对于每个测试用例，输出一行答案，若最长 $\textit{King}$ 子序列长度小于 $\frac{n}{2}$，则输出 $-1$，否则输出最长 $\textit{King}$ 子序列的长度。

由 ChatGPT 4.1 翻译