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

      

    令 Ei=Fi/qi，求Ei。

 

看了很久题解，终于有些眉目，因为知道要用FFT，所以思路就很直了

其实我们就是要±1/(j-i)^2 ( j-i大于0时为正，小于0时为负 ) 和 qi 的乘积要算到j这个位置上，这个满足卷积，所以用FFT优化，但是j-i有负数，所以我们就加上一个n

于是设pi={

i>n,1/(i-n)^2

i<n,-1/(n-i)^2

其他,0

}

然后就套FFT模板就行了

 

1 const 2     maxn=800100; 3 type 4     cp=record 5         x,y:double; 6     end; 7     arr=array[0..maxn]of cp; 8 var 9     a,b,w,tt:arr;10     n,m:longint;11 12 operator -(a,b:cp)c:cp;13 begin14     c.x:=a.x-b.x;15     c.y:=a.y-b.y;16 end;17 18 operator +(a,b:cp)c:cp;19 begin20     c.x:=a.x+b.x;21     c.y:=a.y+b.y;22 end;23 24 operator *(a,b:cp)c:cp;25 begin26     c.x:=a.x*b.x-a.y*b.y;27     c.y:=a.x*b.y+a.y*b.x;28 end;29 30 procedure dft(var a:arr;s,t:longint);31 var32     i,p:longint;33     wt:cp;34 begin35     if n>>t=1 then exit;36     dft(a,s,t+1);dft(a,s+1<
      
       >t>>1-1 do38         begin39             p:=i<
       
        <<1+s;40             wt:=w[i<
        
         <
         
          >t>>1]:=a[p]-wt;43         end;44     for i:=0 to n>>t-1 do45         a[s+i<