$fft$菜题。

题意简述：给一个数列aia_iai​，对于$i=1\to n$求出ansi=∑i&lt;jai(i−j)2−∑i&gt;jai(i−j)2ans_i=\sum_{i&lt;j}\frac{a_i}{(i-j)^2}-\sum_{i&gt;j}\frac{a_i}{(i-j)^2}ansi​=∑i<j​(i−j)2ai​​−∑i>j​(i−j)2ai​​

---

思路：

考虑分开求减号前后的两组和。

前面的直接是一个卷积的形式，后面的可以把$a$数组翻转一下也是一个卷积的形式，然后上$fft$求即可。

代码：

#include
    
     #define ri register intusing namespace std;const double pi=acos(-1.0);const int N=1e5+5;struct cp{
        double x,y;    cp(double _x=0,double _y=0):x(_x),y(_y){
    }    friend inline cp operator+(const cp&a,const cp&b){
    return cp(a.x+b.x,a.y+b.y);}    friend inline cp operator-(const cp&a,const cp&b){
    return cp(a.x-b.x,a.y-b.y);}    friend inline cp operator*(const cp&a,const cp&b){
    return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}    friend inline cp operator/(const cp&a,const double&b){
    return cp(a.x/b,a.y/b);}}a[N];vector
     
      pos;vector
      
       A,B;int lim,tim,n;inline void init(const int&up){
        lim=1,tim=0;    while(lim<=up)lim<<=1,++tim;    pos.resize(lim),A.resize(lim),B.resize(lim),pos[0]=0;    for(ri i=0;i
       
        >1]>>1)|((i&1)<<(tim-1));}inline void fft(vector
        
         &a,const int&type){
        for(ri i=0;i
         
          
           a; poly(int k=0,cp x=cp(0,0)){ a.resize(k+1),a[k]=x;} inline cp&operator[](const int&k){ return a[k];} inline const cp&operator[](const int&k)const{ return a[k];} inline int deg()const{ return a.size()-1;} inline poly extend(const int&k){ poly ret=*this;return ret.a.resize(k+1),ret;} friend inline poly operator*(const poly&a,const poly&b){ int n=a.deg(),m=b.deg(); init(n+m); for(ri i=0;i<=n;++i)A[i]=a[i]; for(ri i=0;i<=m;++i)B[i]=b[i]; for(ri i=n+1;i