这基本上是我在波兰信息学奥林匹克竞赛中被赋予的任务，现在已经结束了。这些值应为模 M(给定)。它现在已经结束了，我知道我需要以某种方式使用 FFT 算法来解决 O(Nlog(N)) 复杂性。
N- 是 2 的幂 (N <= 2^20) 和 (q^N mod M) = 1;
- 这些值是给定的 (q) 的 1 到 N 的幂。例如 当 q=5 且 N=3 时，输出应包含： F(q^1 mod M)、F(q^2 mod M)、F(q^3 mod M)。
- A1，A2...aN 在输入中给出(多项式中的常数)
蛮力将是 N^2，这太慢了。我认为基数-2 算法非常适合，但我不知道它将如何为我提供解决方案，因为在 FFT 中使用复数。
你将使用的算法与FFT几乎相同，但你使用残基mod M而不是复数。 如果添加 M 是素数并且所有q^i都是不同的 modM的其他约束，那么你将得到一个数论变换：
https://www.nayuki.io/page/number-theoretic-transform-integer-dft
但是，您并不严格需要这些额外的约束来解决您的问题。
首先，因为基于 1 的索引很烦人，所以我将把你的 a[N] 称为a[0]，我将把你的第 N个输出移到索引0的开头，因为它使下面的讨论变得容易得多。
所以你想要：
输出[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] 的公式，您可以通过将系数a[...]乘以1， q， q^2来制作out[j]+1的公式,...因此，如果我们有办法计算偶数输出，我们可以将其应用于那些修改后的系数来计算奇数输出。
现在，对于偶数输出，q的所有幂都是 q^2 的幂，它们重复是因为 q^N = q^0 mod 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 的工作原理，那么你现在可能会看到如何将它应用于你的问题。