[ZJOI2014]力

题目大意：

给定\(q_{1\sim n}(n\le10^5)\)，求\(g_i=\sum_{j<i}\frac{q_j}{(i-j)^2}+\sum_{i>j}\frac{q_j}{(i-j)^2}\)。

思路：

令\(f_i=\frac1{i^2}\)，则

\[ g_i=\sum_{j=0}^{i-1}q_if_{i-j}-\sum_{j=i+1}^nq_jf_{j-i} \]

令\(p\)为\(q\)的翻转，\(a_i\)表示前半个和式，\(b_i\)表示后半个和式翻转，则

\[ a_i=\sum_{j=0}^{i-1}q_if_{i-j} \]

\[ b_i=\sum_{j=0}^{i-1}p_if_{i-j} \]

用FFT即可求出。

时间复杂度\(\mathcal O(n\log n)\)。

源代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}inline double getdouble() {    double x;    scanf("%lf",&x);    return x;}const int N=262144;const double pi=M_PI;typedef std::complex
         
           comp;int lim;double ans[N];comp q[N],ru[N],iru[N],p[N],f[N],a[N],b[N];inline void init_ru(const int &n) { for(register int i=0;i
          
           j) std::swap(f[i],f[j]); for(register int l=n>>1;(j^=l)
           
            >=1); } for(register int i=2;i<=n;i<<=1) { const int m=i>>1; for(register int j=0;j