BZOJ3527 [Zjoi2014]力(洛谷3338)

FFT背板题

Posted by yjjr's blog on January 11, 2018

标签:FFT

题目

题目传送门

题目描述

给出n个数qi,给出Fj的定义如下:

输入输出格式 输入格式:

第一行一个整数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。

分析

注意:本题卡精度且数组需要开大

那么

C[i]已经是标准的卷积形式了,D[i]也可以转换,都用FFT就可以辣

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#define pi acos(-1)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=3e5+6;
typedef complex<double> E;
int n,m,L;double x;
E f[maxn],ft[maxn],g[maxn],e1[maxn],e2[maxn];
int rev[maxn];

void fft(E *a,int f){
	rep(i,0,n-1)if(i>rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1){
		E wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<n;j+=(i<<1)){
			E w(1,0);
			for(int k=0;k<i;k++,w*=wn){
				E x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y,a[j+k+i]=x-y;
			}
		}
	}
	if(f==-1)rep(i,0,n-1)a[i]/=n;
}

int main()
{
	n=read();n--;m=2*n;
	rep(i,0,n){
		scanf("%lf",&x);
		f[i]=x;ft[n-i]=x;
	}
	rep(i,1,n)g[i]=(1.0/i/i);
	for(n=1;n<=m;n<<=1)L++;
	rep(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	fft(f,1);fft(g,1);fft(ft,1);
	rep(i,0,n-1)e1[i]=f[i]*g[i];
	rep(i,0,n-1)e2[i]=ft[i]*g[i];
	fft(e1,-1);fft(e2,-1);
	rep(i,0,m/2)printf("%.3lf\n",e1[i].real()-e2[m/2-i].real());
	return 0;
}
		

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr