43. Multiply Strings [Leetcode] [FFT] [python]
查看题目：https://leetcode.com/problems/multiply-strings/description/
粗略步骤：
- 将多项式从系数形式转换为点值形式
- 将两个多项式的点值形式相乘
- 将相乘后的点值形式转换为系数形式
1. 将多项式从系数表示转为点值表示
系数表示： A(x) = a_0 + a_1x + a_2x^2 + ··· + a_{n-1}x^{n-1}
点值表示：(x_0,A(x_0))、(x_1,A(x_1)、···)数个这样的点值对
这里我们巧妙地选择点值表示中的x值：
选择1的n次单位根
1的n次单位根：ω^n = 1，共有n个不同的根
即ω^k_n = cos(2πk/n) + i * sin(2πk/n)
其中i^2 = -1
那么A(ω) = a_0 + a_1ω + a_2ω^2 + ··· + a_{n-1}ω^{n-1}
系数向量\vec a = (a_0, a_1, ··· , a_{n-1})
值向量\vec A = (A(ω_n^0), A(ω_n^1), ··· , A(ω_n^{n-1}))
即\vec A = DFT(\vec a)
这里我们称为离散傅里叶变换
A1 = dft(a1)
A2 = dft(a2)2. 把两个多项式的点值表示相乘
for i in range(n):
A[i] = A1[i]*A2[i]3. 将相乘后的点值表示转为系数表示
离散傅里叶变换亦可表示为矩阵形式W \cdot \vec{a} = \vec{A}。 亦即，
\begin{bmatrix} 1&1&···&1\\ 1&\omega_n^1&···&(ω_n^1)^{n-1}\\ &&···&\\ 1&ω_n^{n-1}&···&(ω_n^{n-1})^{n-1}\end{bmatrix} * \begin{bmatrix} a_0\\ a_1\\ ···\\ a_{n-1}\end{bmatrix} = \begin{bmatrix} A(ω_n^0)\\ A(ω_n^1)\\ ···\\ A(ω_n^{n-1})\end{bmatrix}。
其中，
\vec a = (a_0, a_1, ···, a_{n-1})^\top，
而
\vec A = (A(ω_n^0), A(ω_n^1), ···, A(ω_n^{n-1}))^\top。
其乘积结果为：
$\begin{cases}
a_k = (x_0 + x_2 + ··· + x_{n-2}) \
- ω^{-k} (x_0i - x_2i + ··· + (-1)^{m+2}x_{2m)i}) \
- ω^{-2k}(x_0 - x_2 + ··· + (-1)^m x_{2m})) \
\quad (k=0, 1, ..., n-3)
\end{cases}$
那么 \vec a = W^{-1} * \vec A
即\vec a = DFT^{-1}(\vec A)
这里我们称离散傅里叶逆变换
a = idft(A)a就是相乘后多项式的系数向量
快速傅里叶变换和逆变换
1. FFT
FFT（快速傅里叶变换）是对DFT的优化，减少了乘的次数
1的n次单位根有很好的性质：
ω_n^0 = 1
ω_n^{k+n} = ω_n^k
ω_n^{k+n/2} = -ω_n^k
ω_n^k = (ω_n^1)^k
ω_n^{mk} = ω_{n/m}^k
将多项式按奇偶次项分类后得到两个多项式 A_1(x) 和 A_2(x)：
\begin{aligned} &A_1(x) = a_0 + a_2 x^2 + \cdots +a_{n-3} x^{n-3}+a_{n-1} x^{n-1},\\ &A_2(x) =a_{1} x+a_{3} x^3+\cdots+a_{n-4} x^{n-4}+a_{n-5} x^{n-5}. \end{aligned}
则原多项式可表示为：
A(x)= A₁(x²)+xA₂(x²)
对于任意k=0, 1, ..., n/₂−₁时，
A(ω_nᵏ)= A₁(ω_n²ᵏ)+ ω_nᵏ A₂(ω_n²ᵏ)
接下来
有性质
A(ω_n^k) = A1(ω_{n/2}^k) + ω_n^kA2(ω_{n/2}^k)
有性质
A(ω_n^{k+n/2}) = A1(ω_n^{2k+n}) + ω_n^{k+n/2}A2(ω_n^{2k+n}) = A1(ω_n^{2k}) + ω_n^{k+n/2}A2(ω_n^{2k})
有性质
A(ω_n^{k+n/2}) = A1(ω_{n/2}^k) - ω_n^kA2(ω_{n/2}^k)
通过分治，递归处理。在求出A(ω_n^k)的同时，根据性质，也可以求出A(ω_n^{k+n/2})
2. IFFT
傅里叶变换为
有性质
W = \begin{bmatrix} 1&1&···&1\\ 1&ω_n^1&···&ω_n^{n-1}\\ &&···&\\ 1&ω_n^{n-1}&···&ω_n^{(n-1)(n-1)}\end{bmatrix}
傅里叶逆变换为
有公式W_n(ω)^{-1} = 1/nW_n(ω^{-1})
并且(ω_n^k)^{-1} = cos(2πk/n) - i * sin(2πk/n)
仅需对正变换的结果进行简单的调整即可完成傅里叶逆变换。应将频率变量ω替换为它的倒数即ω^{-1}。特别重要的是，在最终结果中必须进行除以n的操作。
Solution
class Solution:
# opt为1表示傅里叶变换，-1表示逆变换
def fft(self,num,opt):
n = len(num)
if n == 1:
if opt == 1:
return [complex(int(num[0]),0)]
else:
return [num[0]]
#根据奇偶，对半分
A1 = self.fft(num[::2],opt)
A2 = self.fft(num[1::2],opt)
w1 = complex(math.cos(2*math.pi/n),opt*math.sin(2*math.pi/n))
w = complex(1,0)
A = [0]*n
for i in range(0, n//2):
A[i] = A1[i] + w*A2[i]
A[i+n//2] = A1[i] - w*A2[i]
w = w * wn
return A
def multiply(self, num1, num2):
length = len(num1) + len(num2)
n = 1
while n < length:
n = n<<1
# n即相乘后的位数，满足相乘后不会溢出，并且是2的幂次方
A1 = self.fft(num1.zfill(n)[::-1],1)
A2 = self.fft(num2.zfill(n)[::-1],1)
A = [0]*n
for i in range(n):
A[i] = A1[i]*A2[i]
Ans = self.fft(A,-1)
rtn = ''
#up用来进位
up = 0
for num in Ans:
hre = int(num.real/n+0.5+up)
if hre >= 10:
up = int(hre/10)
rtn += str(int(hre%10))
else:
up = 0
rtn += str(hre)
rtn = rtn[::-1].lstrip('0')
# 避免在结果为0时返回空串
if rtn == '':
return '0'
return rtn需要注意的地方
- 数字被以字符串形式输入，并且需要将反转后的字符串与相应的系数进行匹配。
- 相乘操作可能导致结果的长度增加，并且结果的长度必须是2的幂次方。为了满足这一要求，在前面添加零来满足长度需求。
- 计算得到最终的系数向量后，特别地，在处理过程中如果某个系数超过10，则需执行进位操作。