[ZJOI2014]力

题目描述

给出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 }Fj=∑i<j(i−j)2qiqj−∑i>j(i−j)2qiqj$

令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]

显然的卷积形式，第一个多项式是题目中给出的，第二个可以是 -1/(n-1)^2 * x^-(n-1) + ... 0*x^0+ 1/1^2 * x^1 +..... 1/(n-1)^2 * x^(n-1)

#include<bits/stdc++.h>
#define maxn 660005
#define E complex<double>
using namespace std;
const double pi=-acos(-1);
double now;
E a[maxn],b[maxn];
int n,m,l,r[maxn],B,C;

inline void FFT(E *c,int f){
	for(int i=0;i<n;i++) if(i<r[i]) swap(c[i],c[r[i]]);
	
	for(int i=1;i<n;i<<=1){
		E omega(cos(pi/i),f*sin(pi/i));
		for(int p=i<<1,j=0;j<n;j+=p){
			E O(1,0);
			for(int k=0;k<i;k++,O*=omega){
				E x=c[k+j],y=c[k+j+i]*O;
				c[k+j]=x+y;
				c[k+j+i]=x-y;
			}
		}
	}
	
	if(f==-1) for(int i=0;i<n;i++) c[i]/=n;
}

int main(){
	scanf("%d",&n),n--;
	for(int i=0;i<=n;i++){
		scanf("%lf",&now);
		a[i]=now;
	}
	
	B=n,C=B<<1;
	m=n<<1;
	for(int i=0;i<n;i++) b[i]=-1/(double)(B-i)/(double)(B-i);
	for(int i=n+1;i<=m;i++) b[i]=1/(double)(B-i)/(double)(B-i);
	m+=n;
	
	for(n=1,l=0;n<=m;n<<=1) l++;
	for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	
	FFT(a,1),FFT(b,1);
	for(int i=0;i<n;i++) a[i]*=b[i];
	FFT(a,-1);
	
	for(int i=B;i<=C;i++) printf("%lf
",a[i].real());
	
	return 0;
}