多项式乘法

题目描述

给定一个n次多项式F(x)，和一个m次多项式G(x)。

请求出F(x)和G(x)的卷积。

输入输出格式

输入格式：

 

第一行2个正整数n,m。

接下来一行n+1个数字，从低到高表示F(x)的系数。

接下来一行m+1个数字，从低到高表示G(x))的系数。

 

输出格式：

 

一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。

 

输入输出样例

输入样例#1： 

1 21 21 2 1

输出样例#1： 

1 4 5 2

说明

保证输入中的系数大于等于 0 且小于等于9。

对于100%的数据： $n, m \leq {10}^6$ , 共计20个数据点，2s。

数据有一定梯度。

空间限制：256MB

 

---

　　分析：

　　没错，这是一道FFT模板，于是我们愉快地用NTT把它A了。

　　平常用的较多的都是FFT，但是FFT使用的是复数，需要开double类型，常数会比较大。但有时候我们需要求的都是整型，那么用NTT（快速数论变换）就可以把常数降低很多。具体实现理论和FFT基本无异，不过我们要把单位根换成原根，因为原根也满足单位根的性质，最后就可得到一个结论：$w_n \equiv g^{\frac {p-1} {n}} \pmod p$。具体的理论推荐。（吐槽一句，为什么开了O2之后不管是FFT还是NTT都反而更慢了？？？难道是我的代码写得太优秀？？？）

　　Code：

 

#include
     
      using namespace std;typedef long long ll;const int N=3e6+7;const int mod=998244353;int n,m,lim,r[N];int G=3,Gi=332748118;ll a[N],b[N];inline ll read(){    char ch=getchar();ll num=0;bool flag=false;    while(ch<'0'||ch>'9'){
   if(ch=='-')flag=true;ch=getchar();}    while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}    return flag?-num:num;}inline void Swap(ll &x,ll &y){    x^=y,y^=x,x^=y;}inline ll power(ll x,ll y){    ll ret=1;    while(y){        if(y&1)ret=(ret*x)%mod;        y>>=1;x=(x*x)%mod;}    return ret;}inline void ntt(ll *A,int type){    for(int i=0;i
      
       >1]>>1)|((i&1)<<(n-1));    ntt(a,1);ntt(b,1);    for(int i=0;i