分治乘法

这种算法在多项式长度较小且模数对fft不友好时有点用。

多项式f(x)和g(x)折半,假设原来长度为n,变成$(a(x)*x^{n/2}+b(x))*(c(x)*x^{n/2}+d(x))$

拆开括号,变成$a(x)c(x)*x^n+(b(x)c(x)+a(x)d(x))x^{n/2}+b(x)d(x)$

这样子似乎无法化简。

但是可以继续拆成$a(x)c(x)*x^n+b(x)d(x)+(a(x)*x^{n/2}-b(x))*(c(x)*x^{n/2}-d(x))$

这样子只需要3次多项式乘法即可计算。

原文地址:https://www.cnblogs.com/cszmc2004/p/13062529.html