现有两个无序整数集合 \(a\), \(b\)，判断二者是否相同。
可以使用 \(hash\)：钦定一个质数 \(P\) 与模数 \(M\)，对两个集合分别求：
\[(\sum_{i=1}^{n}P^{r_{i}})\space mod \space M
\]
看结果是否相同即可。
题目：link
相当于是要求解 \(n\) 元一次方程，给了 \(n-1\) 个等式和所有解的集合，解方程。首先可以消元，将 \(n-1\) 个未知数都表示成关于同一个未知数 \(r\) 的形式，然后可以枚举 \(r\)，看形成的未知数集合是否与给定的未知数集合相同即可。那么如何快速判断两个集合是否相同就成为了解决此题的关键。可以注意到消元后的未知数形式是有一定规律的：奇数位置 \(r\) 的系数一定是 \(1\), 偶数位置 \(r\) 的系数一定是 \(-1\)。那么我们可以按奇偶先将形成的未知数集合分成两部分，其中系数为 \(-1\) 的集合大致可表示为：
\[P^{c_{1} - r}, P^{c_{2} - r}...P^{c_{m}-r}
\]
它们的和可以表示为：
\[\frac{\sum_{i=1}^{m}P^{c_{i}}}{P^{r}}
\]
分子是可以直接预处理出来的，因此每次枚举 \(r\)，可以 \(O(1)\) 求出奇数位置的和；对于所有系数为 \(1\) 的偶数位置也是同理。这样就可以 \(O(1)\) 判断形成的集合是否与原未知数集合相同。具体细节见代码。
code