题目描述
给出 \(n\) 个数 \(q_1,q_2, \dots q_n\)，定义
\[F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2} \]\[E_i~=~\frac{F_i}{q_i} \]对 \(1 \leq i \leq n\)，求 \(E_i\) 的值。
\(1\leq n\leq 10^5\)
题解
对于乘积形式的式子计算，数据范围 \(10^5\)，应该想到 \(FFT\) 加速。于是开始推式子。
首先\(E_i=\frac{F_j}{q_i}=\sum\limits_{i = 1}^{j - 1} \frac{q_i}{(i - j)^2}~-~\sum\limits_{i = j + 1}^{n} \frac{q_i}{(i - j)^2}\)。
令 \(f(i)=q_i\),\(g(i)=\frac{1}{i^2}\)，于是原式为\(E_i=\sum\limits_{i=1}^{j-1}f(i)\times g(j-i)-\sum\limits_{i = j + 1}^{n}f(i)\times g(i-j)\)。
左边已经是一个卷积的形式了，来看看右边。
卷积形式是从零开始的，我们要尽量将式子化成卷积。
于是更改求和为：\(\sum\limits_{i=0}^{n-j}f(j+i)\times g(i)\)。
接下来是一个经典套路，可以将式子翻转使得\(f'(i)=f(n-i)\)，得到\(\sum\limits_{i=0}^{n-j}f'((n-j)-i)\times g(i)\)
两者都是卷积形式，fft$加速一下即可。
小结：
- fft加速乘法卷积
- 乘号两边同加减的可以翻转式子
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=400010;
const double pai=acos(-1);
int n,rev[N];
struct cp{
double x,y;
cp (double xx=0,double yy=0){x=xx,y=yy;}
cp operator +(cp a){return cp(x+a.x,y+a.y);}
cp operator -(cp a){return cp(x-a.x,y-a.y);}
cp operator *(cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N],b[N],c[N];
void fft(cp *f,int n,int flg){
for(int i=0;i<n;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
for(int p=2;p<=n;p<<=1){
int len=p>>1;
cp tg(cos(2*pai/p),flg*sin(2*pai/p));
for(int k=0;k<n;k+=p){
cp buf(1,0);
for(int l=k;l<k+len;l++){
cp tt=buf*f[len+l];
f[len+l]=f[l]-tt;
f[l]=f[l]+tt;
buf=buf*tg;
}
}
}
if(flg==-1)for(int i=0;i<n;i++)f[i].x/=n;
return ;
}
signed main(){
n=rd();
for(int i=1;i<=n;i++){
scanf("%lf",&a[i].x),c[n-i].x=a[i].x;
b[i].x=1.0/i/i;
}
int lim=1,L=0;
while(lim<=(n<<1))lim<<=1,L++;
for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
fft(a,lim,1),fft(b,lim,1),fft(c,lim,1);
for(int i=0;i<lim;i++)a[i]=a[i]*b[i],c[i]=c[i]*b[i];
fft(a,lim,-1),fft(c,lim,-1);
for(int i=1;i<=n;i++)printf("%.3lf\n",a[i].x-c[n-i].x);
return 0;
}