CF1893A Anonymous Informant

给定一个数组 $b_1, b_2, \ldots, b_n$。 一位匿名线人告诉你，数组 $b$ 是通过如下方式获得的：最初存在一个数组 $a_1, a_2, \ldots, a_n$，然后对其进行了 $k$ 次如下的两步操作： 1. 选择数组 $a$ 的一个不动点 $^\dagger$ $x$。 2. 然后将数组 $a$ 向左循环移动 $^\ddagger$ 恰好 $x$ 次。 经过 $k$ 次这样的操作后，得到了数组 $b_1, b_2, \ldots, b_n$。你需要判断匿名线人的说法是否有可能为真，或者一定为假。 $^\dagger$ 如果 $1 \leq x \leq n$ 且 $a_x = x$，则称 $x$ 是数组 $a_1, a_2, \ldots, a_n$ 的一个不动点。 $^\ddagger$ 数组 $a_1, a_2, \ldots, a_n$ 的一次循环左移是指变为 $a_2, \ldots, a_n, a_1$。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n, k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^9$），分别表示数组 $b$ 的长度和操作次数。 每个测试用例的第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 10^9$），表示数组 $b$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果匿名线人的说法有可能为真，输出 "Yes"；如果一定为假，输出 "No"。

在第一个测试用例中，数组 $a$ 可以为 $[3, 2, 3, 4, 3]$。第一次操作选择了不动点 $x = 2$，经过 $2$ 次左移后，数组变为 $[3, 4, 3, 3, 2]$。第二次操作选择了不动点 $x = 3$，经过 $3$ 次左移后，数组变为 $[3, 2, 3, 4, 3]$。第三次操作再次选择了不动点 $x = 3$，经过 $3$ 次左移后，数组变为 $[4, 3, 3, 2, 3]$，即为数组 $b$。 在第二个测试用例中，数组 $a$ 可以为 $[7, 2, 1]$。经过一次不动点 $x = 2$ 的操作后，数组变为 $[1, 7, 2]$。然后经过一次不动点 $x = 1$ 的操作，数组又回到初始状态 $[7, 2, 1]$。这两步操作（$x = 2$ 和 $x = 1$）重复 $49$ 次。因此，经过 $100$ 次操作后，数组又回到 $[7, 2, 1]$。 在第三个测试用例中，可以证明不存在解。 由 ChatGPT 4.1 翻译