CF1579F Array Stabilization (AND version)

给定一个仅包含 $0$ 和 $1$ 的数组 $a[0 \ldots n-1] = [a_0, a_1, \ldots, a_{n-1}]$。注意，本题中数组下标从 $0$ 开始编号。 每一步操作，将数组 $a$ 替换为另一个长度为 $n$ 的新数组，具体规则如下： 1. 首先，定义新数组 $a^{\rightarrow d}$，它是将数组 $a$ 循环右移 $d$ 位得到的。该数组的元素定义为 $a^{\rightarrow d}_i = a_{(i + n - d) \bmod n}$，其中 $(i + n - d) \bmod n$ 表示 $i + n - d$ 除以 $n$ 的余数。也就是说，整个数组 $a^{\rightarrow d}$ 可以表示为 $[a_{n-d}, a_{n-d+1}, \ldots, a_{n-1}, a_0, a_1, \ldots, a_{n-d-1}]$。 2. 然后，将数组 $a$ 的每个元素 $a_i$ 替换为 $a_i \,\&\, a^{\rightarrow d}_i$，其中 $\&$ 表示按位与运算。 例如，若 $a = [0, 0, 1, 1]$ 且 $d = 1$，则 $a^{\rightarrow d} = [1, 0, 0, 1]$，此时 $a$ 在第一步操作后变为 $[0 \,\&\, 1, 0 \,\&\, 0, 1 \,\&\, 0, 1 \,\&\, 1] = [0, 0, 0, 1]$。 当数组不再发生变化时，过程结束。对于给定的数组 $a$，判断最终数组是否会全部变为 $0$。如果会，请输出该过程所需的步数；否则输出 $-1$。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 接下来的 $2t$ 行描述每个测试用例。 每个测试用例的第一行包含两个整数：$n$（$1 \le n \le 10^6$）表示数组长度，$d$（$1 \le d \le n$）表示循环右移的位数。第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \le a_i \le 1$），表示数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出 $t$ 行，每行一个整数，表示对应测试用例的答案。若最终数组全部变为 $0$，输出所需的步数；若过程结束后数组中仍有 $1$，则输出 $-1$。

在第三个样例测试中，数组变化如下： 1. 初始时 $a = [1, 1, 0, 1, 0]$，$a^{\rightarrow 2} = [1, 0, 1, 1, 0]$。按位与后得到 $[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]$。 2. 现在 $a = [1, 0, 0, 1, 0]$，$a^{\rightarrow 2} = [1, 0, 1, 0, 0]$。按位与后得到 $[1 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 0] = [1, 0, 0, 0, 0]$。 3. 最后 $a = [1, 0, 0, 0, 0]$，$a^{\rightarrow 2} = [0, 0, 1, 0, 0]$。按位与后得到 $[1 \,\&\, 0, 0 \,\&\, 0, 0 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 0] = [0, 0, 0, 0, 0]$。 因此，答案为 $3$ 步。 在第四个样例测试中，数组每次右移 $2$ 位后，所有元素均为 $0 \,\&\, 0$ 或 $1 \,\&\, 1$，因此数组不会发生变化。答案为 $-1$，数组永远不会全为 $0$。 由 ChatGPT 4.1 翻译