struct Polynoial{ struct Complex{ double x,y; Complex(double _x = 0.0,double _y = 0.0){ x = _x; y = _y; } Complex operator-(const Complex &rhs) const{ return Complex(x-rhs.x,y-rhs.y); } Complex operator+(const Complex &rhs) const{ return Complex(x+rhs.x,y+rhs.y); } Complex operator*(const Complex &rhs) const{ return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x); } }; int getSize(int n) { int size = 1; while (size < n) size <<= 1; return size; } void change(vector&a,int n){ for(int i = 1,j = n/2;i < n-1;i++){ if(i < j){ swap(a[i],a[j]); } int k = n/2; while(j >= k){ j -= k; k /= 2; } if(j < k)j += k; } } void fft(vector&a,int n,int opt){ change(a,n); for(int h = 2;h <= n;h*=2){ Complex wn(cos(2*PI/h),sin(opt*2*PI/h)); // 修正:PI/h 而不是 PI/n for(int j = 0;j < n;j+=h){ Complex w(1,0); for(int k = j;k < j+h/2;k++){ Complex u = a[k]; Complex t = w*a[k+h/2]; a[k]=u+t; a[k+h/2]=u-t; w=w*wn; } } } if(opt == -1){ for(int i = 0;i < n;i++){ a[i].x /= n; } } } vector multiply(vector& a, vector& b) { int size = getSize(a.size() + b.size() - 1); vector fa(size), fb(size); for(int i = 0; i < (int)a.size(); i++) fa[i] = Complex(a[i], 0); for(int i = 0; i < (int)b.size(); i++) fb[i] = Complex(b[i], 0); for(int i = a.size(); i < size; i++) fa[i] = Complex(0, 0); for(int i = b.size(); i < size; i++) fb[i] = Complex(0, 0); fft(fa, size, 1); fft(fb, size, 1); for(int i = 0; i < size; i++) { fa[i] = fa[i] * fb[i]; } fft(fa, size, -1); vector res(size); for(int i = 0; i < size; i++) { res[i] = (int)(fa[i].x + 0.5); } return res; } };