UOJ#34. 多项式乘法(FFT&NTT模板)

这是一道模板题。

给你两个多项式,请输出乘起来后的多项式。

输入格式

第一行两个整数 nn 和 mm,分别表示两个多项式的次数。

第二行 n+1n+1 个整数,分别表示第一个多项式的 00 到 nn 次项前的系数。

第三行 m+1m+1 个整数,分别表示第一个多项式的 00 到 mm 次项前的系数。

输出格式

一行 n+m+1n+m+1 个整数,分别表示乘起来后的多项式的 00 到 n+mn+m 次项前的系数。

Solution

推荐一篇博客从多项式乘法到快速傅里叶变换(<–链接请点这里),这篇讲得非常好!

FFT:

NTT:

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注