模板题。。
#include<bits/stdc++.h> using namespace std; typedef int LL; typedef double db; namespace FFT //使用前需要用 fft_init()函数 初始化 { <<; .14159265358979323846264338327950288L; struct cp { db a,b; cp(,) { a=a_,b=b_; } cp operator +(const cp&rhs)const { return cp(a+rhs.a,b+rhs.b); } cp operator -(const cp&rhs)const { return cp(a-rhs.a,b-rhs.b); } cp operator *(const cp&rhs)const { return cp(a*rhs.a-b*rhs.b,a*rhs.b+b*rhs.a); } cp operator !()const { return cp(a,-b); } }nw[FFT_MAXN+],f[FFT_MAXN],g[FFT_MAXN],t[FFT_MAXN]; //a<->f,b<->g,t<->c int bitrev[FFT_MAXN]; void fft_init() //初始化 nw[],bitrev[] { ;<<L)!=FFT_MAXN) L++; ;i<FFT_MAXN;i++) bitrev[i]=bitrev[i>>]>>|((i&)<<(L-)); ;i<=FFT_MAXN;i++) nw[i]=cp((db)cosl(*pi/FFT_MAXN*i),(db)sinl(*pi/FFT_MAXN*i)); } // n已保证是2的整数次幂 // flag=1:DFT | flag=-1: IDFT ) { ;<<d)*n!=FFT_MAXN) d++; ;i<n;i++) if(i<(bitrev[i]>>d)) swap(a[i],a[bitrev[i]>>d]); // NOTICE! ;l<=n;l<<=) { int del=FFT_MAXN/l*flag; // 决定 wn是在复平面是顺时针还是逆时针变化,以及变化间距 ;i<n;i+=l) // ????????????????? { cp *le=a+i,*ri=a+i+(l>>); // ????????????????? cp *w=flag==? nw:nw+FFT_MAXN; // 确定wn的起点 ;k<(l>>);k++) { cp ne=*ri * *w; *ri=*le-ne,*le=*le+ne; le++,ri++,w+=del; } } } ) ;i<n;i++) a[i].a/=n,a[i].b/=n; } // convo(a,n,b,m,c) a[0..n]*b[0..m] -> c[0..n+m] void convo(LL *a,int n,LL *b,int m,LL *c) {//if(n<=100 && m<=100 || min(n,m)<=5) 标程用了直接暴力的方式,或许可以更快 ;; // N+1是c扩展后的长度 ;i<N;i++) // 扩展 a[],b[] ,存入f[],g[] ,以0填充新空间 { f[i]=cp((db)(i<=n? a[i]:),); g[i]=cp((db)(i<=m? b[i]:),); } dft(f,N),dft(g,N); ;i<N;i++) // 频域求积 t[i]=f[i]*g[i]; dft(t,N,-); ;i<=n+m;i++) c[i]=LL(t[i].a+0.5); } } <<|],s2[<<|],s3[<<|]; LL a[<<|],b[<<|],c[<<|]; int main() { FFT::fft_init(); while(~scanf("%s%s",s1,s2)) { memset(s3,,sizeof(s3)); ,m=strlen(s2)-; ;i<=n;i++) a[i]=s1[i]-'; ;i<=m;i++) b[i]=s2[i]-'; FFT::convo(a,n,b,m,c); c[n+m+]=; ;i<n+m-i;i++) swap(c[i],c[n+m-i]); ;i<=n+m;i++) { c[i+]+=c[i]/; c[i]%=; } ; &&len>) len--; ;i--) s3[len-i]=c[i]+'; s3[len+]=; puts(s3); } }