SplittingFoxes2

作者：何中天 钟知闲

关键字：数学，FFT，暴力

题目简述

$n$ 个格子围成一个圆，编号 $0$ 到 $n-1$。用 $p_i$ 表示 $i$ 号格子上的数，$p_i$ 是非负整数。这个圆圈关于 $0$ 号位置对称，即 $p\_{i \bmod n} = p\_{(-i) \bmod n}$。

现在给出将 $p$ 数组做一次循环卷积后的数组 $a$，求可能的 $p$ 数组中字典序最小的。如果没有，返回 $-1$。

$n \le 25, 0\le a_i \le 10^6$。

算法

$\mathrm{DFT}(a) = \mathrm{DFT}(p) * \mathrm{DFT}(p)$

$p = \mathrm{inverseDFT} ( \sqrt{\mathrm{DFT}(a)} )$

在sqrt的时候，每一项都有正负两种取值，如果 $2^n$ 暴力枚举直接超时。

因为 $p$ 是关于 $0$ 对称的，可以发现 $\mathrm{DFT}(p)$ 也是关于 $0$ 对称的，所以只用枚举 $O(2^{\frac{n}{2}+1})$ 次。

由于 $n$ 不一定是 $2$ 的整数次幂， 所以直接写一个 $O(n^2)$ 的 DFT 就好了。

因为 $p_i$ 是非负整数，所以求出来的需检验。

时间复杂度 $O(2^{\frac{n}{2} + 1}n^2)$。

另一种实现

我们可以使用一种不需要考虑精度问题（不涉及浮点数运算）的实现方法，即使用数论变换（NTT）。

首先我们可以选取一个质数 $P$，满足 $n|P-1$，然后在模 $P$ 意义下做 DFT 和 IDFT。单位根可以用原根来代替，两者的等价性这里不再赘述。因为如果 $p_i > 10^3$，那么 $a\_{2i\bmod n} > 10^6$，矛盾，所以只要所取的 $P > 10^3$，那么对于实数意义下成立的解 $\{p_i\}$，在模意义下不需要对 $\{p_i\}$ 取模也一定成立。

这样按照之前的方法求出 $O(2^{\frac{n}{2}+1})$ 种可能的解并一一验证即可。现在的问题在于，如何实现求平方根的操作。实际上就是对于 $y$，枚举所有可能的 $x$，使得 $x^2 \equiv y \pmod P$。

显然在模意义下一个数的平方根不会超过两个（设 $x_1,x_2$ 是 $y$ 的模平方根，则 $x_1^2 - x_2^2 \equiv 0 \pmod P$，即 $P|(x_1+x_2)(x_1-x_2)$，所以 $x_2\equiv x_1$ 或 $x_2\equiv -x_1$），因此可以像实数平方根一样枚举正负。至于如何求模平方根，由于 $P\le 10^3$，可以暴力 $O(P)$ 预处理每个 $[0,P)$ 内的数的平方以得到平方根。

时间复杂度 $O(2^{\frac{n}{2} + 1}n^2 + \sqrt{a_i})$。