algorithm - 如何使用FFT算法计算N个给定特定点的N次多项式值

Question

这基本上是我在波兰的信息学奥林匹克竞赛中被赋予的任务，现在已经结束了。这些值应该是模 M(给定)。现在结束了，我知道我需要使用 FFT 算法以 O(Nlog(N)) 的复杂度来解决它。

1. N 是 2 的幂 (N <= 2^20) 且 (q^N mod M) = 1;
2. 这些值是给定的 (q) 从 1 到 N 的幂。例如当 q=5 和 N=3 时，输出应包含:F(q^1 mod M), F(q^2 mod M),F(q^3 mod M)。
3. a1,a2...aN 在输入中给出(多项式中的常数)

蛮力将是 N^2，那太慢了。我认为 radix-2 算法非常适合，但我不知道它如何为我提供解决方案，因为在 FFT 中你使用复数。

Answer 1

您将使用的算法与 FFT 几乎相同，但您使用的是残数模 M 而不是复数。如果您添加额外的约束条件，即 M 是质数并且所有 q^i 都不同 mod M，那么您将有一个数论转换:

https://www.nayuki.io/page/number-theoretic-transform-integer-dft

但您并不严格需要这些额外的约束来解决您的问题。

首先，因为基于 1 的索引很烦人，我将把您的 a[N] 称为 a[0]，并且我'我打算将您的第 N 输出移动到索引 0 的开头，因为它使下面的讨论变得容易得多。

所以你想要:

out[0] = a[0] + a[1] + a[2] ... a[i] ... a[N-1]

out[1] = a[0] + a[1]*q + a[2]*q^2 ... a[i]*q^i ... a[N-1 ]*q^(N-1)

...

out[j] = ... + a[i]*q^(ij) ...

请注意，如果您有任何 out[j] 的公式，您可以通过乘以系数 来得到 out[j]+1 的公式a[...] by 1, q, q^2,... 所以如果我们有办法计算偶数输出，我们可以将它应用到那些修改计算奇数输出的系数。

现在，对于偶数输出，q 的所有次方都是 q^2 的次方，并且它们会重复，因为 q^N = q^ 0 模 M。因此，对于偶数输出，无需计算:

out[j] = a[0] + a[1]*q^j + ... + a[N-1]*q^(j(N-1)) ...

我们可以用一半的系数来计算它:

out[j] = (a[0]+a[N/2]) + ... + (a[i]+a[N/2+i])^(q^2) ^(ij/2) ...

那 只是使用q*2 和N/2 而不是q 来解决您的问题> 和 N。

因此，就像 FFT 的(时间抽取版本)一样，您通过将 a[...] 转换为两组新系数来解决您的问题，每组系数减半，然后使用这些系数分别生成偶数和奇数输出两次，解决具有 q^2 和 M/2 的较小问题。

希望对您有所帮助...我知道这很难理解，但如果您已经了解 FFT 的工作原理，那么您现在可能会明白如何将其应用到您的问题中。