[ZJOI2014]力 - A-Failure的博客

题目

题目描述

给出n个数qi，给出Fj的定义如下：

$F_j = \sum_{i<j}\frac{q_i q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_i q_j}{(i-j)^2 }$

令Ei=Fi/qi，求Ei.

输入输出格式

输入格式：

第一行一个整数n。

接下来n行每行输入一个数，第i行表示qi。

输出格式：

n行，第i行输出Ei。

与标准答案误差不超过1e-2即可。

输入输出样例

输入样例#1：

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

输出样例#1：

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

说明

对于30%的数据，n≤1000。

对于50%的数据，n≤60000。

对于100%的数据，n≤100000，0<qi<1000000000。

[spj 0.01]

题解

$q_j$直接去掉，发现原式等价于$F_j = \sum_{i=1}^{j-1}\frac{q_{j-i}}{i^2 }-\sum_{i=1}^{n-j}\frac{q_{i+j}}{i^2}$

前面是个卷积的形式，后面把$q$倒过来也是个卷积的形式，直接$FFT$

~~其实是为了水文章~~

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=4e5+5;
const double Pi=acos(-1.0);
struct Complex{
	double x,y;
	Complex(double X=0,double Y=0) {x=X,y=Y;}
}a[MAX],b[MAX],c[MAX];
int n,lim=1,L;
int R[MAX];
double q[MAX],_q[MAX],_[MAX],A[MAX],B[MAX];
Complex operator+ (Complex x,Complex y) {return Complex(x.x+y.x,x.y+y.y);}
Complex operator- (Complex x,Complex y) {return Complex(x.x-y.x,x.y-y.y);}
Complex operator* (Complex x,Complex y) {return Complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
void FFT(Complex *A,int tt=1)
{
	for(int i=0;i<lim;++i)
	  if(i<R[i]) swap(A[i],A[R[i]]);
	for(int i=1;i<lim;i<<=1)
	  {
	  	Complex w1=Complex(cos(Pi/i),tt*sin(Pi/i));
	  	for(int l=i<<1,j=0;j<lim;j+=l)
	  	  {
	  	  	Complex w=Complex(1,0),x,y;
	  	  	for(int k=0;k<i;++k,w=w*w1)
	  	  	  x=A[j+k],y=w*A[i+j+k],A[j+k]=x+y,A[i+j+k]=x-y;
		  }
	  }
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	  scanf("%lf",&q[i]),_q[n-i+1]=q[i],_[i]=1/(double(i)*(i));
	while(lim<=2*n) lim<<=1,++L;
	for(int i=0;i<=lim;++i) 
	  R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
	for(int i=1;i<=n;++i)
	  b[i].x=_[i],a[i].x=q[i],c[i].x=_q[i];
	FFT(a),FFT(b),FFT(c);
	for(int i=0;i<=lim;++i)
	  a[i]=a[i]*b[i],c[i]=c[i]*b[i];
	FFT(a,-1),FFT(c,-1);
	for(int i=1;i<=n;++i)
	  printf("%.5lf\n",(a[i].x-c[n-i+1].x)/lim);
	return 0;
}

题目