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