题解 | H题 Hash Function

有dalao已经贴出来思路和代码了
本鶸看的不太懂，于是又自己百度了百度，学了学，把dalao博客没有细说的部分给详细的讲了讲
当然快速傅里叶变换我也讲的不好，完全不了解的可以去看一看b站上的这个视频
代码我就不写了，是按照之前dalao的代码写的。~~（其实就是写的太烂了）~~

思路

我们可以发现 $a_i \mod{m} \enspace \not = \enspace a_j \mod {m}$ 的充分必要条件是 $|a_i - a_j| \mod {m}\enspace \not = \enspace 0$

可以证明：

不妨假设 $a_j \le a_i$

显然有： $a_j = a_i + a_j - a_i$

可以化为： $a_j = a_i + |a_j - a_i|$

那么 $a_j \mod{m}$ 等价于 $a_i\mod{m} \enspace +\enspace |a_j - a_i| \mod{m}$

所以，只要 $|a_j - a_i| \mod{m} \not = 0$ ，那么 $a_i \mod{m} \not = a_j \mod {m}$

以上证明逐步可逆
所以我们的任务就变为了求出所有的 $|a_i - a_j|$ ,那么如何求出它呢？这时，我们就可以利用离散卷积。

考虑一下卷积的计算过程，假如有序列 $f(n),g(n)$ ,则卷积其卷积为

$y(n) =\displaystyle \sum_{i=-\infty}^{\infty}x(i) * h(n - i)$

可以看出， $y(n)$ 的值是序列 $f, g$ 的所有 *自变量之和为n时,它们的函数值的乘积 *之和

如果我们把给出的自然数映射到新的数组p, $p_i = 1$ 表示数字 $i$ 存在， $p_i = 0$ 等于零表示数字 $i$ 不存在。

我们先来考虑一个类似的问题，假如给定了a,b两个自然数数组，怎么知道a,b两个数组中任意两个数相加后所得到的新数组中都有哪些数呢？

前文说到， $y(n)$ 的值是序列 $f, g$ 的所有 *自变量之和为n时,它们的函数值的乘积 *之和

那么我们分别把a, b两个数组转换为pa, pb数组,对它们进行卷积，得到了数组P

那么我们想一下数组P的每一个数是怎么求出来了，对于 $P_i$ ,它的值为 $\sum pa_x * pa_y$ 其中， $x + y = i$ ,而 $pa_x, pa_y$ 的值只有0，1两中情况，那么 **只有至少有一组 $pa_x, pb_y$ 均为1时, $P_i$ 的值才不为0。**

所以，卷积得到的P数组，其实就是我们需要的结果，只需检查一下P数组的每一个，只要当前下标下的值大于0，那么就意味着这个数存在于新的数组。

那么回到我们现在的问题，我们知道了加法，那么我们如何解决当前这个问题呢？

其实很简单，我们把数组原来的所有数组取相反数，再映射到新的p数组，得到p‘（当然此时的p’数组下标均为负数），那么我们只需要把p和p‘进行卷积，得到的P数组，就是我们要的结果了。

当然因为C++中不能使用负数作为下标，所以我们要做数组平移，即把下标 -x 改为 Max - x，就可以了。
如果我们按照定义的方法去求卷积，其复杂度为 $O(n^2)$ ,是和暴力算法复杂度一样。~~一直以来的努力全部木大~~，但是，离散卷积，刚好就是快速傅里叶变换（FFT）解决多项式相乘问题中的一步。所以我们可以使用FFT来优化离散卷积过程，把时间复杂度降为 $O(nlogn)$ 。

题外话

一个n阶多项式系数数组经过FFT后得到的数组F， $F_i$ 就是 $i$ 阶单位根为自变量的值时，多项式的值。
得到了所有的 $|a_i - a_j|$ 数组，我们只需要找一个不被它们整除的数即可，时间复杂度 $O(nlogn)$ 。