给一个长为 \(n\) 的排列（无序）\(p\)，为 \(p_1, p_2, \cdots, p_n\) 。一个正整数 \(k\) 。
允许执行任意次以下操作：
- 选择两个数 \(p_i\) \(p_j\) 满足 \(|i - j| = k\) ，并且 \(swap(p_i, p_j)\) 。
允许最多执行一次特殊操作：
- 选择两个数 \(p_i\) \(p_j\) ，并且 \(swap(p_i, p_j)\) 。
判断经过上述操作能否使得 \(p\) 有序。如果能，需要执行几次特殊操作。
比较显然排列性质：
让一个排列变为有序，则有：
- \(\forall i, idx = i\) 的数会落在 \(idx = p_i\) 。
\(k\) 给定，则所有 \(i\) 满足 \(k\ |\ |p_i - i|\) 的都是 \(good\) ，最终可以回到正确位置。可以统计出 \(bad\) 的 \(i\) 个数。
记得智商上线，排列也是组合数学。
显然，当 \(bad \geq 3\) ，一定无解。
- 证明：\(good\) 的 \(i\) 已经落在正确位置，此时有 \(\geq 3\) 的位置是错排的，无法通过一次交换使他们回到正确位置。
不存在 \(bad = 1\) 。
- 证明：若 \(n - 1\) 个位置上是正确数的，则剩下的一个位置留给剩下的一个值，也一定是正确的数。
若 \(bad = 2\) ，可以通过一次交换回到正确位置。
- 证明：\(bad = 2\) 代表最终只有两个位置不对，交换这两个数后后位置一定正确。
view
#include <bits/stdc++.h>
void solve() {
int n, k; std::cin >> n >> k;
std::vector<int> a(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
int bad = n;
for (int i = 1; i <= n; i++) bad -= (abs(a[i] - i) % k == 0);
if (bad == 0) std::cout << 0 << '\n';
else if (bad == 2) std::cout << 1 << '\n';
else std::cout << -1 << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}