╰(￣▽￣)╭
對于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++) (⊙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！
