多项式乘法

juhugufudu

对于一般多项式可以记为 P(x) = a₀ + a₁x +a₀x² + ... a_n-1x^n-1
但在计算机中，我们存储的是数字，这需要系数表示法和值表示法
A. 系数表示法要建立一个列表，列表里的每一个数的下标表示对应x的次数
B. 值表示法是把x带入求值，一个n次多项式需要n+1个点来表示，所以需要把n+1个不同的x带入进去

多项式的乘法大致步骤：
1，把多项式以系数表示法来表示，长度为n
2，通过把2(n+1)个x带入，得到对应的值
3，对于另一个也这样做
4，把两个多项式所对应的值相乘，得到有2(n+1)个点
5，反求其系数表示法

以上步骤中，最重要的是如何从系数表示法转到值表示法以及如何从值表示法转到系数表示法

从系数表示法转到值表示法：

  P(x) = a₀ + a₁x +a₀x² + ... +a_n-1x^n-1
       我们把p(x)分成奇偶两类
  Pe(x) = a0 + a₂x + a₄x² + .... + a_n-2x^1/2(n/2)
  Po(x) = a1 + a₃x + a₅x² + ... + a_n-1x^1+1/2(n-2)
所以P(x) = pe(x²) + x(po(x²)这下，我们要求pe的值只有n/2个x要求了，但因为pe(x²)中x的取值正还是负得出的结果一样，我们可以再次优化
P(x) = pe(x²) + x(po(x²)
P(x+n/2) = pe(x²) - x(po(x²)
当x取e^2pi*i/n，  xⁿ = 1 （n代表多项式的次数，这里默认为2^m）

我们可以迭代：

def FFT(A):
    n = len(A)
    x = cos(2pi/n) + i*sin(2pi/n)
    po = A[::2]
    pe = A[1::2]
    FFT(po,pe)
   

当n=1 时，说明已经到底层了,这时我们把A看作是一个一次函数，并求x = +1,-1的值

def FFT(A):
    if n==1:
        return A
    n = len(A)
    x = cos(2pi/n) + i*sin(2pi/n)
    po = A[::2]
    pe = A[1::2]
    FFT(po)
    FFT(pe)
    for j in range(0,n):
        A[j] = pe[j] + x[sup]j[/sup]*po[j]
        A[j+n/2] = pe[j] - x[sup]j[/sup]*po[j]
       

说完了从系数表示法转到值表示法，我们把变换后的值在变换回去：首先，我们要把刚才做的事用数学符号描述出来：

https://www.bilibili.com/video/BV1za411F76U

把这个过程倒过来，便是求关于w的矩阵的逆我们可以大致猜一下他的逆：

def FFT(A):
    if n==1:
        return A
    n = len(A)
    x = cos(2pi/n) - i*sin(2pi/n)
    po = A[::2]
    pe = A[1::2]
    FFT(po)
    FFT(pe)
    for j in range(0,n):
        A[j] = pe[j] + x[sup]j[/sup]*po[j]
        A[j+n/2] = pe[j] -x[sup]j[/sup]*po[j]

      

在最后，把处理完的A的每一项都除以n就可以了