今天的A题，裸的ntt，但我不会，于是白送了50分。
于是跑来学一下ntt。
题面很简单，就懒得贴了，那不是我要说的重点。
重点是NTT，也称快速数论变换。
在很多问题中，我们可能会遇到在模意义下的多项式乘法问题，这时传统的快速傅里叶变换可能就无法满足要求，这时候快速数论变换就派上了用场。
考虑快速傅里叶变换的实现，利用单位复根的特殊性质来减少运算，而利用的，就是dft变换的循环卷积特性。于是考虑在模意义下同样具有循环卷积特性的东西。
考虑在模p意义下(p为特定的质数，满足p=c∗2n+1)
我们令p的一个原根为g,于是类比fft，我们的单位根为gp−1n,然后其它的处理都类比fft。
UPD:这是uoj34的代码 #include using namespace std; typedef long long ll; typedef double db; const int inf=0x3f3f3f3f; int getint() { int f=1,g=0;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0' && c<='9')g=(g<<3)+(g<<1)+c-'0',c=getchar(); return f*g; } const int maxn=300005; const int mod=998244353; const int G=3; int a[maxn]; int b[maxn]; int c[maxn]; int n,m; int rev[maxn]; int N; int len; int inv; int power(ll x,ll y) { ll res=1ll; for(;y;y>>=1,x=(x*x)%mod) { if(y&1)res=(res*x)%mod; } return res; } void init() { while((n+m)>=(1<1<2); for(int i=0;iint pos=0; int temp=i; for(int j=1;j<=len;j++) { pos<<=1;pos |= temp&1;temp>>=1; } rev[i]=pos; } } void ntt(int *a,int n,int re) { for(int i=0;iif(rev[i]>i) { swap(a[i],a[rev[i]]); } } for(int i=2;i<=n;i<<=1) { int mid=i>>1; int wn=power(G,(mod-1)/i); if(re) wn=power(wn,(mod-2)); for(int j=0;jint w=1; for(int k=0;kint temp1=a[j+k]; int temp2=(ll)a[j+k+mid]*w%mod; a[j+k]=(temp1+temp2);if(a[j+k]>=mod)a[j+k]-=mod; a[j+k+mid]=(temp1-temp2);if(a[j+k+mid]<0)a[j+k+mid]+=mod; w=(ll)w*wn%mod; } } } if(re) { for(int i=0;i*inv%mod; } } } int main() { n=getint(); m=getint(); for(int i=0;i<=n;i++) { a[i]=getint(); } for(int i=0;i<=m;i++) { b[i]=getint(); } init(); ntt(a,N,0); ntt(b,N,0); for(int i=0;i<=N;i++) { c[i]=(ll)a[i]*b[i]%mod; } ntt(c,N,1); for(int i=0;i<=n+m;i++) { printf("%d%c",c[i]," "[i==n+m]); } return 0; }