题目
题目链接：https://www.luogu.com.cn/problem/P3338
给出 \(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\) 的值。
思路
\[E_j=\frac{\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}}{q_i}
\]
\[=\sum_{i = 1}^{j - 1} \frac{q_i}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i}{(i - j)^2}
\]
令 \(f(i)=q_i,g(i)=\frac{1}{i^2}\)，则
\[=\sum^{j}_{i=0}f(i)\times g(j-i)-\sum^{n}_{i=j}f(i)\times g(i-j)
\]
\[=\sum^{j}_{i=0}f(i)\times g(j-i)-\sum^{n-j}_{i=0}f(i+j)\times g(i)
\]
令 \(h(i)=f(n-i)\)，则
\[==\sum^{j}_{i=0}f(i)\times g(j-i)-\sum^{n-j}_{i=0}h((n-j)-i)\times g(i)
\]
此时原式已经转换为两个卷积之差，用 FFT 优化即可。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
#define cp complex<double>
using namespace std;
const int N=300010;
const double pi=acos(-1);
int n,lim,rev[N];
double q[N];
cp f[N],g[N],h[N];
void fft(cp *f,int inv)
{
for (int i=0;i<lim;i++)
if (rev[i]<i) swap(f[i],f[rev[i]]);
for (int mid=1;mid<lim;mid<<=1)
{
cp temp(cos(pi/mid),inv*sin(pi/mid));
for (int i=0;i<lim;i+=(mid<<1))
{
cp w(1,0);
for (int j=0;j<mid;j++,w*=temp)
{
cp x=f[i+j],y=w*f[i+j+mid];
f[i+j]=x+y; f[i+j+mid]=x-y;
}
}
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf",&q[i]);
for (int i=1;i<=n;i++)
{
f[i]=cp(q[i],0.0);
g[i]=cp(1.0/i/i,0.0);
h[i]=cp(q[n-i+1],0.0);
}
lim=1;
while (lim<=(n<<1)) lim<<=1;
for (int i=0;i<lim;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
fft(f,1); fft(g,1); fft(h,1);
for (int i=0;i<lim;i++)
f[i]*=g[i],h[i]*=g[i];
fft(f,-1); fft(h,-1);
for (int i=1;i<=n;i++)
printf("%0.8lf\n",(f[i].real()-h[n-i+1].real())/lim);
return 0;
}