Description

Input

輸入文件包含一個整數(shù)n，接下來n行每行輸入一個數(shù)，第i行表示qi。

Output

輸出文件有n行，第i行輸出Ei。與標(biāo)準(zhǔn)答案誤差不超過1e-2即可。

Sample Input

5

4006373.885184

15375036.435759

1717456.469144

8514941.004912

1410681.345880

Sample Output

-16838672.693

3439.793

7509018.566

4595686.886

10903040.872

Data Constraint

對于30%的數(shù)據(jù)，n≤1000。

對于50%的數(shù)據(jù)，n≤60000。

對于100%的數(shù)據(jù)，n≤100000，0

Solution

• 經(jīng)典FFT……

• 先推式子，化簡一下 Ei ，得：

  Ej=∑i<jqi(j?i)2?∑i>jqi(i?j)2

• 可以發(fā)現(xiàn)前面和后面是差不多的，我們可以分開算。

• 現(xiàn)在考慮前面，有：

  Pj=∑i<jqi(j?i)2

• 令 ri=1i2 ，則有標(biāo)準(zhǔn)數(shù)論卷積的形式：

  Pj=∑i<jqi?rj?i

• 如此一來就可以直接用FFT加速計(jì)算了，時間復(fù)雜度 O(N?log?N) 。

• 而后面部分就相當(dāng)于把 q<script type="math/tex" id="MathJax-Element-533">q</script> 數(shù)組反過來做一遍即可。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<cmath> using namespace std; const int N=1e5+5; const double Pi=acos(-1.0); struct comp {double r,i;comp(){}comp(double rr,double ii){r=rr,i=ii;}comp operator +(const comp &x)const{return comp(r+x.r,i+x.i);}comp operator -(const comp &x)const{return comp(r-x.r,i-x.i);}comp operator *(const comp &x)const{return comp(r*x.r-i*x.i,i*x.r+r*x.i);} }f1[N<<2],f2[N<<2],f3[N<<2]; int n,m; int rev[N<<2]; double q[N]; inline double read() {double X=0,Y=1.0; int w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();ch=getchar();while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();return w?-X:X; } inline void FFT(comp *y,int ff) {for(int i=0;i<m;i++)if(i<rev[i]) swap(y[i],y[rev[i]]);for(int h=2;h<=m;h<<=1){comp wn(cos(2*Pi/h),ff*sin(2*Pi/h));for(int i=0;i<m;i+=h){comp w(1,0);for(int k=i;k<i+h/2;k++){comp u=y[k],t=w*y[k+h/2];y[k]=u+t;y[k+h/2]=u-t;w=w*wn;}}}if(ff==-1) for(int i=0;i<m;i++) y[i].r/=m; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) q[i]=read();int l=0;for(m=1;m<=n<<1;m<<=1) l++;for(int i=0;i<m;i++) rev[i]=rev[i>>1]>>1|(i&1)<<l-1;for(int i=1;i<=n;i++) f1[i]=comp(q[i],0);for(int i=1;i<=n;i++) f2[i]=comp(q[n-i+1],0);for(int i=1;i<=n;i++) f3[i]=comp(1.0/i/i,0);FFT(f1,1),FFT(f2,1),FFT(f3,1);for(int i=0;i<m;i++) f1[i]=f1[i]*f3[i];for(int i=0;i<m;i++) f2[i]=f2[i]*f3[i];FFT(f1,-1),FFT(f2,-1);for(int i=1;i<=n;i++) printf("%.3lf\n",f1[i].r-f2[n-i+1].r);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 3617. 【ZJOI2014】力的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。