题目理解

我们有两个多重集 $S$ 和 $T$，大小均为 $n$。
可以对 $S$ 中的某个元素 $x$ 做如下操作：

• 删除 $x$，然后插入 $x+k$ 或 $|x-k|$。

问：能否经过任意次操作，使 $S$ 变成 $T$？

---

关键数学观察

操作的本质是：
$x$ 可以变成 $x+k$ 或 $|x-k|$。
考虑 $x$ 对 $k$ 取模：

设 $r = x \bmod k$（$0 \le r < k$）。

• $x+k$ 对 $k$ 取模仍是 $r$。
• $|x-k|$ 对 $k$ 取模是 $(k-r) \bmod k$，即 $0$ 或 $k-r$。

重要结论：
一个元素 $x$ 可以变成另一个元素 $y$ 当且仅当

$$x \equiv y \pmod{k} \quad \text{或} \quad x + y \equiv 0 \pmod{k}. $$

证明

1. 若 $x \equiv y \pmod{k}$
   假设 $x < y$，可以反复执行 $x \to x+k$，直到变成 $y$。
   若 $x > y$，则反复执行 $x \to |x-k|$ 并注意控制方向，可以归约到 $y$。

2. 若 $x + y \equiv 0 \pmod{k}$
   可以先将 $x$ 变成 $x \bmod k$（通过反复减去 $k$ 或变成 $|x-k|$ 来调整），
   再变成 $z = (k - (x \bmod k)) \bmod k$，此时 $z \equiv y \pmod{k}$，
   再利用情况 1 变成 $y$。

---

化简思路

因此，对于任意元素 $x$，我们可以只关注它在模 $k$ 意义下的最小非负代表，但注意：

由于 $x$ 可以变成 $x \bmod k$ 或 $(k - (x \bmod k)) \bmod k$，
这两个值中更小的那个就是它能达到的“最简形式”。

定义：

$$f(x) = \min(x \bmod k,\; (k - (x \bmod k)) \bmod k) $$

为什么取 $\min$？
因为 $x \bmod k$ 和 $k - (x \bmod k)$ 两者代表的“剩余类”在操作下是等价的（互变），所以我们统一映射到较小的那个，用于比较两个多重集是否可能相等。

---

算法步骤

1. 读入 $n, k$ 和两个多重集 $A$（原 $S$）和 $B$（目标 $T$）。
2. 对 $A$ 中每个元素 $x$，计算 $r = x \bmod k$，再计算 $val = \min(r, k-r)$，用哈希表计数 $cnt[val]++$。
3. 对 $B$ 中每个元素 $x$，同样计算 $val$，然后 $cnt[val]--$。
4. 如果最终哈希表中所有计数都为 $0$，说明 $A$ 和 $B$ 在“最小代表”意义下匹配，输出 "YES"，否则 "NO"。

---

为什么用随机哈希（XOR RD）

题目中 $k$ 可达 $10^9$，$val$ 的范围是 $0 \le val \le \lfloor k/2 \rfloor$，直接用 $val$ 做哈希键没问题，但为了防止卡哈希（hacking 或刻意构造冲突），代码中用了一个随机数 $RD$，将键变成 $val \oplus RD$，这样攻击者无法预知哈希函数。

在 C++ 中，直接用 $val$ 也可以 AC，但加上随机化更安全。

---

例子验证

样例 3

$S = [6,2,9],\; T = [8,4,11],\; k=5$

• $6 \bmod 5 = 1$，$\min(1,4)=1$
• $2 \bmod 5 = 2$，$\min(2,3)=2$
• $9 \bmod 5 = 4$，$\min(4,1)=1$

$A$ 的计数：$\{1:2,\;2:1\}$

• $8 \bmod 5 = 3$，$\min(3,2)=2$
• $4 \bmod 5 = 4$，$\min(4,1)=1$
• $11 \bmod 5 = 1$，$\min(1,4)=1$

$B$ 的计数：$\{2:1,\;1:2\}$

完全匹配 $\to$ YES

---

复杂度

• 每个元素 $O(1)$ 处理。
• 总复杂度 $O(n)$。
• 满足 $n$ 总和 $\le 2\times 10^5$。

---

最终代码（C++，无随机化简化版，易于理解）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> A(n), B(n);
        for (int i = 0; i < n; i++) cin >> A[i];
        for (int i = 0; i < n; i++) cin >> B[i];
        
        map<int, int> cnt;
        
        for (int x : A) {
            int r = x % k;
            cnt[min(r, k - r)]++;
        }
        
        for (int x : B) {
            int r = x % k;
            cnt[min(r, k - r)]--;
        }
        
        bool ok = true;
        for (auto& [_, v] : cnt) {
            if (v != 0) {
                ok = false;
                break;
            }
        }
        
        cout << (ok ? "YES" : "NO") << '\n';
    }
    
    return 0;
}

---