如何用FFT算法计算给定点的N次多项式值
这基本上就是我在波兰的信息学奥林匹克运动会上的任务，现在已经结束了。值应该是模M(给定)。现在结束了，我知道我需要用FFT算法来解决O(Nlog(N))复杂度的问题。
- N是2 (N <= 2^20)的幂，(q^N mod M) = 1；
- 该值是(q)的1到N的幂，这是given.For的例子，当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中使用复数一样。
回答 1
Stack Overflow用户
发布于 2018-04-17 00:44:42
您将使用的算法与FFT基本相同，但您使用的是残差mod M，而不是复数。如果添加M是素数的附加约束，并且所有q^i都是不同的mod M，则将进行数论转换：
https://www.nayuki.io/page/number-theoretic-transform-integer-dft
但你并不完全需要那些额外的约束来解决你的问题。
首先，因为基于1的索引很烦人，所以我将把您的aN称为a，然后将Nth输出移到Index的起始位置，因为它使下面的讨论变得非常容易。
所以你想：
out =a+ a1 + a2 .哎..。aN-1
out1 =a+ a1*q + a2*q^2艾Q^我..。aN-1*q^(N-1)
…
outj =.+ ai*q^(ij) .
请注意，如果您有任何outj的公式，则可以通过将系数a.乘以1、q、q^2、…，从而得到outj+1的公式。因此，如果我们有一种方法计算偶数输出，我们可以将其应用于那些修改的系数来计算奇数输出。
对于偶数输出，q的所有幂都是q^2的幂，因为q^N = q^0 mod M。因此，对于偶数输出，而不是计算：
outj =a+ a1*q^j +.+ aN-1*q^(j(N-1)) .
我们可以用一半的系数来计算，比如：
outj = (a+aN/2) +.+ (ai+aN/2+i)^(q^2)^(ij/2) .
这只是使用q*2和N/2来解决您的问题，而不是使用q和N。
因此，就像(时间抽取) FFT一样，通过将a.转换成两个新的系数集，每个系数的一半大小，解决问题，然后用q^2和M/2两次解决较小的问题，使用这些系数分别生成偶数和奇数输出。
希望这能帮上忙..。我知道这很难理解，但是如果您已经了解FFT的工作原理，那么现在您可能可以看到如何将它应用于您的问题了。
https://stackoverflow.com/questions/49855284
复制相似问题
腾讯云开发者
