P3338 [ZJOI2014]力
斯德哥尔摩
2018-07-29 10:30:38
[P3338 [ZJOI2014]力](https://www.luogu.org/problemnew/show/P3338)
#### 纪念我的洛谷博客第100篇！
题目要求：$$E_i=\frac{F_i}{q_i},F_i=\sum_{j<i}\frac{q_iq_j}{(i-j)^2}-\sum_{j>i}\frac{q_iq_j}{(i-j)^2}$$
把$F_i$带入得：$$E_i=\sum_{j<i}\frac{q_j}{(i-j)^2}-\sum_{j>i}\frac{q_j}{(i-j)^2}$$
设$r_i=\frac{1}{i^2}$，则：$$E_i=\sum_{j=1}^{i-1}q_jr_{i-j}-\sum_{j=i+1}^{n}q_jr_{j-i}$$
再设$p_i=q_{n-i+1}$，则：$$E_i=\sum_{j=1}^{i-1}q_jr_{i-j}-\sum_{j=i+1}^{n}p_{n-j}r_{j-i}$$
然后我们发现，减号的两边都是卷积的形式。
那怎么求呢？
去吧，**FFT**
于是将$q_i,p_i,r_i$分别作为多项式$A,B,C$的系数。
然后得到$A* C,B* C$的系数。
再将$(A* C)_ i$与$(B* C)_ {n-i+1}$系数相减，即为$E_i$。
然后这题就是FFT的板子了。
注：计算$\frac{1}{i^2}$不能写成$1/(i* i)$，一定要写成$1/i/i$，不然会爆精度的。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN (1<<20)
using namespace std;
int n;
double q[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace FFT{
int n,l,rev[MAXN];
struct node{
double r,i;
node operator +(const node &a)const{return (node){r+a.r,i+a.i};}
node operator -(const node &a)const{return (node){r-a.r,i-a.i};}
node operator *(const node &a)const{return (node){r*a.r-i*a.i,r*a.i+i*a.r};}
}a[MAXN],b[MAXN],c[MAXN],d[MAXN];
void DFT(node *a,int f){
for(int i=0;i<l;i++)d[i]=a[rev[i]];
for(int i=0;i<l;i++)a[i]=d[i];
for(int i=2;i<=l;i<<=1){
node wi=(node){cos(2.00*M_PI/i),sin(2.00*M_PI/i)*f};
for(int k=0;k<l;k+=i){
node w=(node){1.00,0.00},x,y;
for(int j=0;j<i/2;j++){
x=a[k+j];y=w*a[k+j+i/2];
a[k+j]=x+y;a[k+j+i/2]=x-y;
w=w*wi;
}
}
}
if(f==-1)
for(int i=0;i<=l;i++)a[i].r/=l;
}
void FFT(){
DFT(a,1);DFT(b,1);DFT(c,1);
for(int i=0;i<=l;i++){a[i]=a[i]*c[i];b[i]=b[i]*c[i];}
DFT(a,-1);DFT(b,-1);
}
void init(int x){
for(n=l=1;l<x;l<<=1)n++;
l<<=1;
for(int i=0;i<l;i++)
for(int j=0,t=i;j<n;j++,t>>=1){rev[i]<<=1;rev[i]|=t&1;}
}
inline double square(double i){
return ((1.00/i)/i);
}
void DSC(int len){
for(int i=1;i<=len;i++){
a[i].r=b[len-i+1].r=q[i];
c[i].r=square(i);
a[i].i=b[len-i+1].i=c[i].i=0.00;
}
init(len);
FFT();
for(int i=1;i<=len;i++)printf("%.3lf\n",a[i].r-b[len-i+1].r);
}
}
void init(){
n=read();
for(int i=1;i<=n;i++)scanf("%lf",&q[i]);
}
int main(){
init();
FFT::DSC(n);
return 0;
}
```