力 bzoj-3527 Zjoi-2014

题目大意：给定长度为$n$的$q$序列，定义$F_i=\sum\limits_{i<j}\frac{q_iq_j}{(i-j)^2}-\sum\limits_{i>j}\frac{q_iq_j}{(i-j)^2}$。求所有的$E_i=\frac{F_i}{q_i}$。

注释：$1\le n\le 10^5$，$0\le q\le 10^9$。

---

想法：我们可以把$F_i$中每一项上的$q_i$删掉因为我们求得$E_i$除掉了。

进而我们考虑如何求解$F$。

先看$j<i$的部分

$F_i=\sum\limits_{j=0}^{i-1} \frac{q_j}{(i-j)^2}$。

设$p(x)=\frac{1}{x^2}$。

所以$F_i=\sum\limits_{j=0}^{i-1} q_j\cdot p_{i-j}$。

紧接着我们强制令$p_0=0$，$F_i=\sum\limits_{j=0}^i q_j\cdot p_{i-j}$，可以用$FFT$加速。

接下来看$i<j$的部分。

此时$F_i=\sum\limits_{j=i+1}^{n-1} q_j\cdot p_{j-i}$。

像一样，这时我们将$p$序列翻转，仍然可以用$FFT$加速。

之后把这两部分加一起即可。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 100010 using namespace std; typedef double db;const db pi=acos(-1);db E[N<<2],q[N<<2],p[N<<2];struct cp{	db x,y;	cp() {x=y=0;}	cp(db x_,db y_) {x=x_,y=y_;}	cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}	cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}	cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}}a[N<<2],b[N<<2],c[N<<2],d[N<<2];void fft(cp *a,int len,int flg){	int i,j,k,t;	cp tmp,w,wn;	for(i=k=0;i
          
           k) swap(a[i],a[k]); for(j=len>>1;(k^=j)
           
            >=1); } for(k=2;k<=len;k<<=1) { wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k)); t=k>>1; for(i=0;i
            
             > n ; for(int i=0;i
            
           
          
         
        
       
      
     

小结：对于这两种形式可以用$FFT$加速应该熟练掌握。