首页 > 代码库 > BZOJ 3527: [Zjoi2014]力

BZOJ 3527: [Zjoi2014]力

2024-09-06 14:20:54   216人阅读

3527: [Zjoi2014]力

Time Limit: 30 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 1819  Solved: 1077
[Submit][Status][Discuss]

Description

给出n个数qi，给出Fj的定义如下：
技术分享
令Ei=Fi/qi，求Ei.

Input

第一行一个整数n。
接下来n行每行输入一个数，第i行表示qi。
n≤100000，0<qi<1000000000

Output

 n行，第i行输出Ei。与标准答案误差不超过1e-2即可。

Sample Input

5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880

Sample Output

-16838672.693
3439.793
7509018.566
4595686.886
10903040.872

HINT

Source

分析：

$E[i]=\sum _{j<i}\frac {q[j]}{(i-j)^2}-\sum _{j>i}\frac {q[j]}{(i-j)^2}$...

这样我们发现可以写成这种形式：

$E[i]=A[i]-B[i]$

$A[i]=\sum _{j<i}f[j]g[i-j]$

$f[i]=q[i]$，$g[i]=\frac {1}{i^2}$

$B[i]$是一样的只不过把原数列反过来求...

这样就是裸的卷积了...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<complex>#include<cstdio>//by NeighThorn#define pi acos(-1)using namespace std;typedef complex<double> M;const int maxn=300000+5;int n,m,L,R[maxn];M a[maxn],b[maxn],c[maxn];inline void FFT(M *a,int f){	for(int i=0;i<n;i++)		if(i>R[i]) swap(a[i],a[R[i]]);	for(int i=1;i<n;i<<=1){		M wn(cos(pi/i),f*sin(pi/i));		for(int j=0;j<n;j+=(i<<1)){			M w(1,0);			for(int k=0;k<i;k++,w*=wn){				M x=a[j+k],y=w*a[j+k+i];				a[j+k]=x+y,a[j+k+i]=x-y;			}		}	}	if(f==-1)		for(int i=0;i<n;i++)			a[i]/=n;}signed main(void){	double x;	scanf("%d",&n);n--;	for(int i=0;i<=n;i++) scanf("%lf",&x),a[i]=x,c[n-i]=x;	for(int i=1;i<=n;i++) b[i]=1.0/i/i;	m=n<<1;for(n=1;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),FFT(c,1);	for(int i=0;i<n;i++) a[i]*=b[i];	for(int i=0;i<n;i++) c[i]*=b[i];	FFT(a,-1),FFT(c,-1);	for(int i=0;i<=m/2;i++)		printf("%.3f\n",a[i].real()-c[m/2-i].real());	return 0;}

　　

By NeighThorn

BZOJ 3527: [Zjoi2014]力


联系
我们