╰(￣▽￣)╭
对于100%的数据，n≤100000;0<qi<1,000,000,000。
(⊙ ▽ ⊙)
令ri=1i2， 设Fj=∑j−1i=0qi∗rj−1−i，Gj=∑j−1i=0qn−1−i∗rj−i−1。 显然Ei=Fi−Gn−i−1。 像F,G的这样的式子，我称它为卷积式：
当满足f[j]=∑i=0j−1a[i]∗b[j−1−i] 这样的形式时，可以利用快速傅里叶变换： 设多项式A的系数分别为a[0],a[1],a[2],...,a[j−1]， 多项式B的系数分别为b[0],b[1],b[2],...,b[j−1]。 则多项式C(其中C=A∗B)的系数就分别为f[0],f[1],f[2],...,f[j−1]。
(￣～￣)
#include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<string.h>#define ll long longusing namespace std;const char* fin="ex3617.in";const char* fout="ex3617.out";const int inf=0x7fffffff;const int maxn=500007;const double pi=acos(-1);struct Z{ double x,y; Z(double _x=0,double _y=0){x=_x;y=_y;} Z Operator +(const Z &a){return Z(x+a.x,y+a.y);} Z operator -(const Z &a){return Z(x-a.x,y-a.y);} Z operator *(const Z &a){return Z(x*a.x-y*a.y,x*a.y+y*a.x);}}a[maxn],b[maxn],c[maxn],d[maxn];int n,m,i,j,k,r[maxn];void fft(Z *a,int sig){ int i,j,k; for (i=0;i<n;i++) if (r[i]<i) swap(a[r[i]],a[i]); for (i=2;i<=n;i<<=1){ int ha=i/2; for (j=0;j<ha;j++){ Z w(cos(j*pi*sig/ha),sin(j*pi*sig/ha)); for (k=j;k<n;k+=i){ Z u=a[k],v=w*a[k+ha]; a[k]=u+v; a[k+ha]=u-v; } } }}int main(){ scanf("%d",&n); for (i=0;i<n;i++){ scanf("%lf",&a[i].x); c[n-1-i].x=a[i].x; } for (i=1;i<n;i++) b[i]=1.0/i/i; m=n; k=0; for (n=1;n<m<<1;n<<=1) k++; for (i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(k-1)); fft(a,1); fft(c,1); fft(b,1); for (i=0;i<n;i++) a[i]=a[i]*b[i]; for (i=0;i<n;i++) c[i]=c[i]*b[i]; fft(a,-1); fft(c,-1); for (i=0;i<m;i++) PRintf("%lf/n",a[i].x/n-c[m-i-1].x/n); return 0;}(⊙v⊙)
1.
for (i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(k-1));这是一行很强的代码，可以用于求出：二进制数i在k位意义上的倒转r[i] 具体地， 采用递推的形式，r[i]可由r[i shr 1]推得。 实质是i和i shr 1在二进制中十分相似，区别只在于i多了一位数。
2.WARNING 最后的结果一定要/n！
