3527: [Zjoi2014]力

时间：2023-03-10 01:41:35
3527: [Zjoi2014]力

题目大意：给出n个数qi，定义 Fj为

      3527: [Zjoi2014]力

令 Ei=Fi/qi，求Ei。

设A[i]=q[i],B[i]=1/(i^2)。

设C[i]=sigma(A[j]*B[i-j]),D[i]=sigma(A[n-j-1]*B[i-j])。

那么所求的E[i]=C[i]-D[i]。

不难发现C[i]已经是标准的卷积形式了，用FFT即可。

对于D[i],令A'[i]=A[n-i-1]，那么D[i]=sigma(A[j]*B[i-j])，于是也用FFT即可。

code:

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 262144

 #define pi 3.14159265358979323846

 using namespace std;

 char ch;

 int m,n;

 bool ok;

 long double ans[maxn];

 double q[maxn];

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 struct comp{

     long double rea,ima;

     void clear(){rea=ima=;}

     comp operator +(const comp &x){return (comp){rea+x.rea,ima+x.ima};}

     comp operator -(const comp &x){return (comp){rea-x.rea,ima-x.ima};}

     comp operator *(const comp &x){return (comp){rea*x.rea-ima*x.ima,rea*x.ima+ima*x.rea};}

 }a[maxn],b[maxn],c[maxn],tmp[maxn],w,wn;

 void fft(comp *a,int st,int siz,int step,int op){

     if (siz==) return;

     fft(a,st,siz>>,step<<,op),fft(a,st+step,siz>>,step<<,op);

     int x=st,x1=st,x2=st+step;

     w=(comp){,},wn=(comp){cos(op**pi/siz),sin(op**pi/siz)};

     for (int i=;i<(siz>>);i++,x+=step,x1+=(step<<),x2+=(step<<),w=w*wn)

         tmp[x]=a[x1]+(w*a[x2]),tmp[x+(siz>>)*step]=a[x1]-(w*a[x2]);

     for (int i=st;siz;i+=step,siz--) a[i]=tmp[i];

 }

 int main(){

     read(m),n=;

     while (n<(m<<)) n<<=;

     for (int i=;i<m;i++) scanf("%lf",&q[i]); 

     for (int i=;i<n;i++) a[i].clear();

     for (int i=;i<n;i++) b[i].clear();

     for (int i=;i<m;i++) a[i].rea=q[i];

     for (int i=;i<m;i++) b[i].rea=1.0/i/i;

     fft(a,,n,,),fft(b,,n,,);

     for (int i=;i<n;i++) c[i]=a[i]*b[i];

     fft(c,,n,,-);

     for (int i=;i<m;i++) ans[i]=c[i].rea/n; 

     for (int i=;i<n;i++) a[i].clear();

     for (int i=;i<n;i++) b[i].clear();

     for (int i=;i<m;i++) a[i].rea=q[m-i-];

     for (int i=;i<m;i++) b[i].rea=1.0/i/i;

     fft(a,,n,,),fft(b,,n,,);

     for (int i=;i<n;i++) c[i]=a[i]*b[i];

     fft(c,,n,,-); 

     for (int i=;i<m;i++) printf("%.9lf\n",(double)(ans[i]-c[m-i-].rea/n));

     return ;

 }

相关文章