1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include<bits/stdc++.h> #ifndef M_PI #define M_PI 3.14159265358979323846 #endif using namespace std; int n,m; struct fushu { double x,y; }f[4000005],g[4000005]; fushu operator+(fushu a,fushu b){return (fushu){a.x+b.x,a.y+b.y};} fushu operator-(fushu a,fushu b){return (fushu){a.x-b.x,a.y-b.y};} fushu operator*(fushu a,fushu b){return (fushu){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};} void fft(int lim,fushu *a,int tp) { if(lim==1)return ; fushu a1[lim>>1],a2[lim>>1]; for(int i=0;i<=lim;i+=2) a1[i>>1]=a[i],a2[i>>1]=a[i+1]; fft(lim>>1,a1,tp); fft(lim>>1,a2,tp); fushu Wn=(fushu){cos(2.0*M_PI/lim),tp*sin(2.0*M_PI/lim)},w=(fushu){1.0}; for(int i=0;i<(lim>>1);i++,w=w*Wn) { a[i]=a1[i]+w*a2[i]; a[i+(lim>>1)]=a1[i]-w*a2[i]; } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) scanf("%lf",&f[i].x); for(int i=0;i<=m;i++) scanf("%lf",&g[i].x); int lim=1; while(lim<=n+m) lim<<=1; fft(lim,f,1); fft(lim,g,1); for(int i=0;i<=lim;i++) f[i]=f[i]*g[i]; fft(lim,f,-1); for(int i=0;i<=n+m;i++) printf("%.0lf ",floor(f[i].x/lim)); }
|