題目大意:給定n個點,第i個點和第j個點之間的庫侖力為(qi*qj)/(i-j)^2,定義左側為正方向,求每個點受的合力與電荷量的比值
#include#include #include #include #include #define M 263000 #define PI 3.1415926535897932384626433832795028841971 using namespace std; struct Complex{ long double a,b; Complex() {} Complex(long double _,long double __):a(_),b(__) {} Complex operator + (const Complex &x) const { return Complex(a+x.a,b+x.b); } Complex operator - (const Complex &x) const { return Complex(a-x.a,b-x.b); } Complex operator * (const Complex &x) const { return Complex(a*x.a-b*x.b,a*x.b+b*x.a); } void operator *= (const Complex &x) { *this=(*this)*x; } }a[M],b[M],c[M]; int n; long double q[M],ans[M]; void FFT(Complex x[],int n,int type) { static Complex temp[M]; if(n==1) return ; int i; for(i=0;i >1]=x[i],temp[i+n>>1]=x[i+1]; memcpy(x,temp,sizeof(Complex)*n); Complex *l=x,*r=x+(n>>1); FFT(l,n>>1,type);FFT(r,n>>1,type); Complex root(cos(type*2*PI/n),sin(type*2*PI/n)),w(1,0); for(i=0;i >1;i++,w*=root) temp[i]=l[i]+w*r[i],temp[i+(n>>1)]=l[i]-w*r[i]; memcpy(x,temp,sizeof(Complex)*n); } int main() { int i,digit; double x; cin>>n; for(digit=1;digit<=n<<1;digit<<=1); for(i=0;i