实用算法 003:高斯消元算多项式乘法
众所周知ntt/fft是目前已知的时间复杂度最优的多项式乘法算法。
那为什么我们还需要知道这个方法呢?
考虑这个问题:
有(n)个多项式(p_1,p_2,p_3...p_n)。和一个目标多项式(q),初始(q=1)
有(q)次操作:(mul i)。
表示令(q=q imes p_i)。
最后输出(q)的前(a)次项系数。(保证乘法过程中大于a次项系数都为0)
直接fft/ntt时间复杂度为(O(aqlog a))。但是fft/ntt的常数巨大,经常会TLE。
下面介绍一种小常数(O(a^3+a imes q))的做法。
设最终的多项式(q=sum a_{i} imes x^i)。
我们若令(x=1,2,3,4...a),然后将(x^i)看作常数,(a_i)看作未知数,列出(a)个方程,然后高斯消元即可。可以发现最终的矩阵一定是非奇异的,所以方程一定存在唯一解。
适用范围:
乘法次数多,系数非0的项的个数比较少。
题目: cf917d